4527.sagews

def rsaParameters(p,q,e):
    print 'one computes n=p*q=',p,'*',q,'=',p*q
    n=p*q
    print
    print 'one computes φ(n)=(p-1)(q-1)=',p-1,'*',q-1,'=',(p-1)*(q-1)
    print
    print 'one checks that e (=',e,') is actually coprime with φ(n) since gcd(e,φ(n))=',gcd(e,(p-1)*(q-1)) ,'and one computes its inverse d= e^(-1) mod φ(n).'
    print 'For this, one may use the extended Euclidean algorithm, or d=1/mod(e,φ(n))=',1/mod(e,(p-1)*(q-1))
    d=1/mod(e,(p-1)*(q-1))
    print
    print 'Finally, the public key is Ke=(e,n)=(',e,',',p*q,'). The private key is Kd=(d,n)=(',d,',',n,').'
    return d

d=rsaParameters(47,59,17)

one computes n=p*q= 47 * 59 = 2773 one computes φ(n)=(p-1)(q-1)= 46 * 58 = 2668 one checks that e (= 17 ) is actually coprime with φ(n) since gcd(e,φ(n))= 1 and one computes its inverse d= e^(-1) mod φ(n). For this, one may use the extended Euclidean algorithm, or d=1/mod(e,φ(n))= 157 Finally, the public key is Ke=(e,n)=( 17 , 2773 ). The private key is Kd=(d,n)=( 157 , 2773 ).

def RSAencryption(m,e,n): #
    print 'Encryption: one computes',m,'^',e,'mod', n,'=',mod(m^e, n)
    encr=mod(m^e, n)
    return encr

c=RSAencryption(66,17,2773)

Encryption: one computes 66 ^ 17 mod 2773 = 872

# one computes c^d mod n and one checks that it is actually equal to the original message
RSAencryption(c,157,2773)

Encryption: one computes 872 ^ 157 mod 2773 = 66 66