Week 4 Friday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

Slide 4

Deepnote notebook#

!pip install pycryptodome

Collecting pycryptodome
  Downloading pycryptodome-3.18.0-cp35-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (2.1 MB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 2.1/2.1 MB 78.3 MB/s eta 0:00:00
?25hInstalling collected packages: pycryptodome
Successfully installed pycryptodome-3.18.0
WARNING: You are using pip version 22.0.4; however, version 23.2 is available.
You should consider upgrading via the '/root/venv/bin/python -m pip install --upgrade pip' command.


from Crypto.Util.number import getPrime, getRandomNBitInteger
from sympy.ntheory import n_order, nextprime, isprime

I highly recommend printing the primes so you can recover them if necessary.

p = getPrime(100)
q = getPrime(100)
N = p*q
phiN = (p-1)*(q-1)
print(p)
print(q)

873113365496510728361088335653
1189460389891662892796812437329

from math import gcd

for e in range(3, 20):
    print(e, gcd(e, phiN))

3 3
4 4
5 1
6 6
7 1
8 8
9 3
10 2
11 1
12 12
13 1
14 2
15 3
16 16
17 1
18 6
19 1

# NOT USEFUL NOT USEFUL NOT USEFUL
for e in range(3, 20):
    print(e, gcd(e, N))

3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1

# Based on the gcd(e, phiN) computation
e = 5
d = pow(e, -1, phiN)

d

830827011314481294653786259977914037286262685751664862414285

phiN

1038533764143101618317232824972392546607828357189581078017856

# Posted by Bob (these roles are not well-defined)
print(N)
print(e)

1038533764143101618317232824974455120363216530810738978790837
5

# Alice chooses a secret number x, smaller than N
x = getRandomNBitInteger(150)
x

1038901915847095962934390886653578512618574104

# How does Alice encrypt x? Formula can't involve phi(N) phiN because phiN is not public
c = pow(x, e, N)
c # gets posted publicly

358949600211821129437967767338529861170448579055271971144791

# How does Bob find x from c?
pow(c, d, N)

1038901915847095962934390886653578512618574104

Break until 10:12am#

from math import sqrt

p = 873113365496510728361088335653
q = 1189460389891662892796812437329
N = p*q
phiN = (p-1)*(q-1)

b = phiN - N - 1
c = N

(-b + sqrt(b**2 - 4*c))/2

1.189460389891663e+30

(-b - sqrt(b**2 - 4*c))/2

8.731133654965107e+29

from numpy import sqrt

(-b + sqrt(b**2 - 4*c + 0.))/2

1.189460389891663e+30

5/2

2.5
Created in deepnote.com Created in Deepnote