Chapter 08 - Cryptography.sagews

Chapter 8 - Cryptography

Example 8.4 (affine cipher)

Encryption

mod(9*1+18,26)

1

mod(9*6+18,26)

20

mod(9*6+18,26)

20

mod(9*9+18,26)

21

P=[1, 6, 6, 9, 14, 5, 3, 9, 16, 8, 5, 18];
[mod(9*n+18,26) for n in P]

[1, 20, 20, 21, 14, 11, 19, 21, 6, 12, 11, 24]

Decryption

C=[1, 20, 20, 21, 14, 11, 19, 21, 6, 12, 11, 24];
[mod(3*(n-18),26) for n in C]

[1, 6, 6, 9, 14, 5, 3, 9, 16, 8, 5, 18]

Example 8.9 (Pohlig - Hellman)

Prime and exponent selection

next_prime(746380674)

746380697

︠0d0f5ca0-2cf9-4d05-9b25-d3ace8b96e19︠
gcd(153,746380696)

1

Encryption

P=[16151225,7180116,80903];
[n.powermod(153,746380697) for n in P]

[586932278, 13007814, 458837458]

Decryption exponent computation

solve_mod(2* x == 1, 7)

[(4,)]

xgcd(153,746380696)

(1, 360994585, -74)

C=[586932278, 13007814, 458837458];
[n.powermod(360994585,746380697) for n in C]

[16151225, 7180116, 80903]

Massey-Omura exchange

Example 8.11 (Massey-Omura exchange)

We encrypt, putting the 'first lock' on:

123456789.powermod(85479892289,41889443039)

19155614901

Next we put the second lock on:

19155614901.powermod(46828919,41889443039)

6133869575

Next we find the inverse of the first encryption exponent:

xgcd(85479892289,41889443038)

(1, -8974971613, 18314390241)

mod(-8974971613,41889443038)

32914471425

We decrypt, removing the first lock:

6133869575.powermod(32914471425,41889443039)

2121551126

We find the second decryption exponent:

xgcd(46828919,41889443038)

(1, -9309559951, 10407315)

mod(-9309559951,41889443038)

32579883087

We remove the second lock and recover the original plaintext:

 2121551126.powermod(32579883087,41889443039)

123456789

Example 8.15 (RSA algorithm)

We search for some `large' primes using the next_prime command:

next_prime(1234)

1237

next_prime(4321)

4327

We compute n:

1237*4327

5352499

And φ (n):

1236*4326

5346936

We check that our exponent is relatively prime to φ (n):

gcd(101,5346936)

1

Now we encrypt:

12345.powermod(101,5352499)

1676086

Next, we find the decrypting exponent:

xgcd(101,5346936)

(1, -1323499, 25)

mod(-1323499,5346936)

4023437

Now we decrypt to obtain the original plaintext:

1676086.powermod(4023437,5352499)

12345

Notes - Computing Powers Mod p

powers=[57]
for k in [1..6]:
    powers.append(mod((powers[k-1])^2,541))
table([(2^k, powers[k]) for k in [0..6]], header_row=["t", "57^t mod 541"], frame=True)

+----+--------------+ | t | 57^t mod 541 | +====+==============+ | 1 | 57 | +----+--------------+ | 2 | 3 | +----+--------------+ | 4 | 9 | +----+--------------+ | 8 | 81 | +----+--------------+ | 16 | 69 | +----+--------------+ | 32 | 433 | +----+--------------+ | 64 | 303 | +----+--------------+

mod(303*433*81*3*57,541)

496