jsMath

Number Theory - RSA

The following function creates a key with the given number of bits;

for example, if bits equals 10, it creates a key n=pq such that n is approximately 2^{10}=1024.

In real life example, bits should be chosen to be 512, 1024, or 2048 long.
def rsa(bits): # only prove correctness up to 1024 bits proof = (bits <= 1024) p = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof) q = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof) n = p*q phi_n = (p-1)*(q-1) while True: e = ZZ.random_element(1,phi_n) if gcd(e,phi_n) == 1: break d = lift(Mod(e,phi_n)^(-1)) return e, d, n 
       
Mod(2,5)^(-1) 
        
3
rsa(5) 
        
(3, 11, 25)
rsa(10) 
        
(1283, 1251, 2491)
e,d,n = rsa(20) 
       
e,d,n 
        
(40927, 16887, 98191)
factor(n) 
        
149 * 659
rsa(1024) 
        
(6712672420388631454144106927755167311326585969456227336685544513915\
14284068686621339956044197697988471165040850546693078636948634781756\
89328952860378909838518534238900459430834435330686482015166476681833\
79212920401139649530283100287908158150590108769104678279684213083485\
710781728326845905238452050845617037,
26320268287386603580507602110783416269424513278443869227524557760146\
01659788281245924970813368059864674597205087996114927142253895457285\
74172084551797246239667028909996327062095673927290541974795268542179\
89418756420594179255911285316626899578135422622062790889249927065883\
0573478825598943632530274529907813,
69073488828530506581458845193209401736852539776918096591525074013144\
30483536483603964321173646192882258375659117958035170746466706406551\
64071888273859182056361219225806933365472462318601185809529551409558\
34941881195491111245946011774847900055918312489395649299343292617058\
54987100436127511815064358289899819)

The next two functions encrypt a message m using the public key (e,n)

and decrypt the cipher c using the private key d.

 
def encrypt(m, e, n): return lift(Mod(m,n)^e) def decrypt(c, d, n): return lift(Mod(c,n)^d) 
       
e,d,n = rsa(20) 
       
e,d,n 
        
(693361, 58681, 1092407)
c = encrypt(1000,e,n) 
       
c 
        
100736
decrypt(c,d,n) 
        
1000

The next two functions encode and decode a string of ASCII code (such as letters A,B,C,...

and symbols !,..) into a number. Each symbol in ASCII code is assigned a number from

0 to 255. This is transformed into a number using base 256.
def encode(s): s = str(s) return sum(ord(s[i])*256^i for i in range(len(s))) def decode(n): n = Integer(n) v = [] while n != 0: v.append(chr(n % 256)) n //= 256 # this replaces n by floor(n/256) return ''.join(v) 
       
m = encode('Run away!'); m 
        
617488957642785060178
decode(m) 
        
'Run away!'
ord('a') 
        
97
ord('!') 
        
33
chr(33) 
        
'!'
chr(97) 
        
'a'

Now let's do a complete example:

First Alice makes her public and private key.
e,d,n = rsa(1024) 
       
n 
        
19916843653116281670376280837171448938436048081098657621754645956910\
69272285177675793934661908675039892516858388687373498426832140166525\
50760819986595829788119049753441435300586452325900306535250123376657\
85706205007564606932459742475805062593504501312324470178430291386156\
9057246863092659608859833524175647453

She gives Bob her public key (e,n). He then first encodes his message into a number and then encrypts it using

Alice's public key.
m = encode('Meet me at 4.'); m 
        
3660627931379277721006992876877
c = encrypt(m,e,n); c 
        
28138652202951542365663785109537477502048196764120498228575217659208\
22511621626463358408523430635714118910967530795016742534827001535700\
67139420477275939813384614054761653015337627758371523948526612767352\
91363440866244452834176903715764292759908614243148800434392566886574\
146602550773431639536043092865645320

He sends Alice c. Alice then decrypts the message using her private key d that only

she knows.
M = decrypt(c,d,n); M 
        
3660627931379277721006992876877
decode(M) 
        
'Meet me at 4.'

It is hard to factor this big n:
factor(n)