Implementing cryptographic algorithms in SageMath

This worksheet contains

Diffie-Hellman(-Merkle) Key Exchange (1976)
RSA Cryptosystem (Rivest, Shamir, Adleman, 1977)

Homework exercises

ElGamal Cryptosystem (Unlike RSA, ElGamal offers randomized encryption) (1985)
Naor-Pinkas Oblivious Transfer (standard model version, 1999)

In [1]:

%load_ext sage
reset()

Diffie-Hellman-Merkle Key Exchange

Key Exchange protocols allow two parties (Alice and Bob) to establish a shared secret key over a public channel. The shared key is typically used later to encrypt communications using a symmetric cipher. DH key exchange was published in 1977, and it used even today, see for example the SSL/TLS protocol.

Please note that we use $G$ a subgroup of the multiplicative group mod p in this example, but the protocol is generic and works with any cyclic group $G$ . Today, it is more typical to use the group of points on an elliptic curve. For example, see Dan Bernstein's paper Curve25519: new Diffie-Hellman speed records (2006).

Find a cyclic group $G = \lt g \gt$ where discrete logarithm is difficult. In this example, we will use a $384$ -bit safe prime $p = 2q + 1$ and work in the subgroup generated by an element $g \in \mathbb{Z}_p^\times$ of order $q$ . These parameters can be re-used for multiple key exchanges; however, in this case please consider Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice by Adrian et al. (2015).

In [3]:

##generate safe prime p = 2q+1

q_bits = 256
q = random_prime(2^(q_bits-1), 2^q_bits)

while not is_prime(2*q+1):
    q = next_prime(q)
    
p = 2*q+1    

print 'p =',p
print 'q =',q

##find generator g of a q-order subgroup G 
h = mod(primitive_root(p), p) # generator of (Z/pZ)^*
g = h^2                       # generator of G in (Z/pZ)^*

# for demonstration purposes, 
# pick a large generator to make it clear that the dlog is not trivial
g = g^(10000)
print 'g =',g

Out[3]:

p = 114613267282339829338903510180606894251700056873567053286214694567429338735367
q = 57306633641169914669451755090303447125850028436783526643107347283714669367683
g = 14777377999967849666226757901157577468444643860798182661856789517423526464749

Alice picks a random $a \in \mathbb{Z}_q$ and sends $x = g^a$ to Bob.
Bob picks a random $b \in \mathbb{Z}_q$ and sends $y = g^b$ to Alice.
Both Alice and Bob can compute the shared key $g^{ab} = x^b = y^a$ .

In [4]:

## pick a at random and compute x = g^a
a = randint(1,q)
x = g^a
print 'a =',a
print 'x =',x

## pick b at random and compute y = g^b
b = randint(1,q)
y = g^b
print
print 'b =',b
print 'y =',y

## verify that the shared keys match
print
print 'shared keys:'
print y^a
print x^b
print 'do both keys match?', y^a==x^b

Out[4]:

a = 15764173127667486369388209701790495254322923469351346598298572844464806486635
x = 22884344087133916710922209329334559797932787184156132248161196101948804732757

b = 54320806754993796302089388319171462146586564968605097944283930867831526385909
y = 51836811621591415653636009627025018775489124390529408109860956025701440804324

shared keys:
58583507538462285032111108391630946943078928404088383347364084865112949235881
58583507538462285032111108391630946943078928404088383347364084865112949235881
do both keys match? True

RSA Cryptosystem

RSA is (one of?) the first asymetric encryption algorithm.

The public key is a product of two large primes $n = pq$ and a small prime exponent, typically $e = 2^{16}+1 = 65537$ .

Private key $d \equiv e^{(-1)} \pmod{\varphi(n)}$ , where $\varphi(n) = (p-1)(q-1)$ is the order of multiplicative group mod $n$ . It is easy to compute the inverse, when factorization of $n$ is known, using the extended euclidean algorithm.

In [5]:

n_bits = 1024

p = random_prime(2^(n_bits/2))
q = random_prime(2^(n_bits/2))
n = p*q
e = 2^16+1
print 'n =',n
print 'e =',e

d = lift(mod(e,(p-1)*(q-1))^(-1))
print
print 'd =',d

Out[5]:

n = 10375814577185727341213388232242994981078976766282449996551113660038324467955853708418610396159522660856258990049469650959585349536774832598717526096491439697067572078467925360821319023706063982859855273906529550080660356883492506844455336277876725073980220315720193794825608574850285570490746757532857840257
e = 65537

d = 5276803940638117281575937711226620423872961771521339981766767143584194493445971040810416779895278854484323544537418915520743697454273237568324078685262666421313127972780073445282936006834141092379690261445644313086219029934893245060578175709058527975648648626285084299409139524563007052970025410502365340873

Encryption and decryption

To encrypt a message $M \in \{1, \ldots, n-1\}$ , you compute hte e-th power of M (mod n).

$C \equiv M^e \pmod{n}$ .

So, to decrypt a cryptotext $C$ , you have to compute its $e$ -th root. $M' \equiv C^d \pmod{n}$ .

$M' \equiv C^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M . M^{\varphi(n)k} \equiv M \pmod{n}$

In [6]:

# encryption
M = mod(randint(1,n-1),n)
C = M^e
print 'M =',M
print 'C =',C

# decryption
Mprime = C^d
print 'M\' =',Mprime
print 'Did decryption succeed? ',Mprime==M

Out[6]:

M = 7653968902662302370440769446462578537018267475903579447179619895063797985058713196137681883352326566029050391199042340678333294430153518409600647725776555251108340105553612036661528665360673503554924208491143338241369257365790534364070713504705594301999813708791065029338728207032523942029301587247772509645
C = 294150992329392823966357357895110459066602570592425514300666707814930173900643725226223735567083343417725265649083363414277457754738638023119287351578038071572377508628473424363767666018873333362708484798056096226782584145057829037351120406651682302139498817740659962667970299579695247667672937406003781677
M' = 7653968902662302370440769446462578537018267475903579447179619895063797985058713196137681883352326566029050391199042340678333294430153518409600647725776555251108340105553612036661528665360673503554924208491143338241369257365790534364070713504705594301999813708791065029338728207032523942029301587247772509645
Did decryption succeed?  True

In [ ]:

Implementing cryptographic algorithms in SageMath

Diffie-Hellman-Merkle Key Exchange

RSA Cryptosystem

Encryption and decryption

Product

Resources

Company