Crypto + Group Theory + Python (computer language)
Kirby Urner
urner at alumni.princeton.edu
Mon Apr 2 18:07:58 EDT 2001
An introductory 4-part essay beginning at:
http://www.inetarena.com/~pdx4d/ocn/crypto0.html
This essay provides a fairly standard slice through crypto
+ group theory, at an introductory level, with the added
benefit of working Python source code providing an interactive
command line experience (once you have Python set up on your
own computer that is -- it's not interactive over the web).
The approach is to start with simple letter substitions, in
order to introduce cyclic notation for permutations (also
presented as substitution dictionaries). This thread is
developed to where we get an Enigma-style encryption machine
(in software of course) by Part 4.
I also get into residue classes as a good alternative example
of a group, and touch on fields and rings briefly (including
Galois fields). This thread is developed into a presentation
of the RSA algorithm (in simple form, minus any worries about
block chaining etc.).
Any feedback welcome. The main point of the paper is to show
how a computer language like Python has gotten us to the point
of being able to teach/learn/explore these concepts without to
much noise/static coming from the language itself.
We get an object-oriented paradigm to the extent we need it
(the ciphers.py module is also procedural), plus we get access
to the big numbers (e.g. those 100 digit probable primes).
And finally, Python provides the ability to override primitive
operators (e.g. *), which helps simplify the command line
syntax and make it look pretty much like regular text book
math (except, unlike math typography, it also executes).
Example:
******************** Permutations
>>> p1 = P()
>>> p2 = P()
>>> p1
Permutation: [('X', 'S', 'I', 'B', 'H', 'A', 'P', 'Q', 'N', 'C'),
('V', 'E', 'F', 'K', 'L', 'U', 'J'), ('T', 'O', 'D'), ('R', 'G', 'M')]
>>> p2
Permutation: [('Z', 'B', 'H', 'G', 'Q', 'K'), ('X', 'Y', 'D', 'L', 'W',
'O', 'S', 'J', 'C', 'T', 'M', 'A', 'P', 'N', 'R', 'U'), ('V', 'F')]
>>> p1*p2
Permutation: [('Z', 'B', 'G', 'A', 'N', 'T', 'S', 'I', 'H', 'P', 'K',
'W', 'O', 'L', 'X', 'J', 'F'), ('Y', 'D', 'M', 'U', 'C'), ('V', 'E'),
('R', 'Q')]
>>>
******************** Residue Classes
>>> r19 = Rgroup(19) # integers 0<n<19 relatively prime to 19
>>> r19.table() # multiplication table a*b = (a*b) mod 19
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
----------------------------------------------------------
1| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
2| 2 4 6 8 10 12 14 16 18 1 3 5 7 9 11 13 15 17
3| 3 6 9 12 15 18 2 5 8 11 14 17 1 4 7 10 13 16
4| 4 8 12 16 1 5 9 13 17 2 6 10 14 18 3 7 11 15
5| 5 10 15 1 6 11 16 2 7 12 17 3 8 13 18 4 9 14
6| 6 12 18 5 11 17 4 10 16 3 9 15 2 8 14 1 7 13
7| 7 14 2 9 16 4 11 18 6 13 1 8 15 3 10 17 5 12
8| 8 16 5 13 2 10 18 7 15 4 12 1 9 17 6 14 3 11
9| 9 18 8 17 7 16 6 15 5 14 4 13 3 12 2 11 1 10
10| 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9
11| 11 3 14 6 17 9 1 12 4 15 7 18 10 2 13 5 16 8
12| 12 5 17 10 3 15 8 1 13 6 18 11 4 16 9 2 14 7
13| 13 7 1 14 8 2 15 9 3 16 10 4 17 11 5 18 12 6
14| 14 9 4 18 13 8 3 17 12 7 2 16 11 6 1 15 10 5
15| 15 11 7 3 18 14 10 6 2 17 13 9 5 1 16 12 8 4
16| 16 13 10 7 4 1 17 14 11 8 5 2 18 15 12 9 6 3
17| 17 15 13 11 9 7 5 3 1 18 16 14 12 10 8 6 4 2
18| 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
>>> r19.powers() # successive powers of the elements
** 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
-------------------------------------------------------------
1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2| 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1
3| 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1
4| 1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1
5| 1 5 6 11 17 9 7 16 4 1 5 6 11 17 9 7 16 4 1
6| 1 6 17 7 4 5 11 9 16 1 6 17 7 4 5 11 9 16 1
7| 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1
8| 1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1
9| 1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1
10| 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1
11| 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1 11 7 1
12| 1 12 11 18 7 8 1 12 11 18 7 8 1 12 11 18 7 8 1
13| 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1
14| 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1
15| 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 1
16| 1 16 9 11 5 4 7 17 6 1 16 9 11 5 4 7 17 6 1
17| 1 17 4 11 16 6 7 5 9 1 17 4 11 16 6 7 5 9 1
18| 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1
Note: generators 2,3,10,13,14,15; alignment of 1s on phi(19)=18.
******************** Enigma
>>> enigma = Enigma((P(),P(),P()))
>>> enigma
Enigma-class object: rotors of order [70, 25, 28]
>>> c = enigma.encrypt("The quick brown fox jumped over the lazy dog")
>>> c
'CUJ IDQCP DWNWO RHL EORPVM JKKZ FRV MUNU DQK'
>>> enigma.reset()
>>> enigma.decrypt(c)
'THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG'
******************** RSA
>>> n,d = rsasetup()
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.174154779666 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.105195360298 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.122132452772 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.0577088117498 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.0670225783215 seconds
OK!
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.16886974304 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.21835934226 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.150248076567 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.20220084145 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.13931678372 seconds
Working...
Percent chance of being prime: 99.9999999999
Elapsed time: 0.0668842923951 seconds
OK!
>>> n
6791173138720358549442154196955776087284943351022541074
90752646923705763811166100361667415958202764041289309L
>>> c = rsaencrypt("Able was I ere I saw Elba",n)
>>> c
26224534259193152535566751829861677229300074664466780250
5662323822190595176483491971842171889130264573428281L
>>> rsadecrypt(c,d,n)
'Able was I ere I saw Elba'
Kirby
More information about the Python-list
mailing list