Week 5 Wednesday#

Screenshare notes#

Slide 1

Slide 2

Slide 3

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 98.7 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.1 is available.
You should consider upgrading via the '/root/venv/bin/python -m pip install --upgrade pip' command.


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

This is very similar to what you do in Part 2 of Lab 5.

Overall: demonstrate how to factor N = p*q given an encryption/decryption pair.

p = getPrime(100)
q = getPrime(100)
N = p*q

N

945579382313214135470583525960206135776873895012524267916947

len(str(N))

60

from math import gcd

# Find e relatively prime to phi(N) = (p-1)*(q-1)
gcd(3, (p-1)*(q-1))

1

e = 3

d = pow(e, -1, (p-1)*(q-1))
d

630386254875476090313722350638807516242010007986054396841611

Now we’re in the context of what we were talking about earlier: we have N, e, and d, and want to demonstrate how to factor N using this knowledge. (The special part is the assumption that we know d.) Notice: we’re not going to use phi(N) in this computation.

p

1219441140946744671516135755963

q

775420272912138361926536898569

# Choose a base x relatively prime to N (very weak restriction)
x = getRandomNBitInteger(80)

gcd(x, N)

1

# Much less likely to be relatively prime to phi(N)
gcd(x, (p-1)*(q-1))

23

x

740736515515552739501307

# No reason to try such a big x, let's just try x = 2
x = 2

pow(x, e*d - 1, N)

1

pow(2, e*d - 1, N)

1

from Lab5_Helper import factor_out_2

factor_out_2(48)

(4, 3)

(2**4)*3

48

factor_out_2(100)

(2, 25)

(2**2)*25

100

factor_out_2(1024)

(10, 1)

(2**10)*1

1024

factor_out_2(e*d-1)

(5, 59098711394575883466911470372388204647688438248692599703901)

(e*d-1)%32

0

(e*d-1)%64

32

pow(2, e*d - 1, N)

1

# Want a^2 = 1 mod N
a = pow(2, (e*d - 1)/2, N)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In [48], line 2
      1 # Want a^2 = 1 mod N
----> 2 a = pow(2, (e*d - 1)/2, N)

TypeError: pow() 3rd argument not allowed unless all arguments are integers

# Only use `x//y` if you know y divides x
a = pow(2, (e*d - 1)//2, N)

pow(a, 2, N)

1

a

1

# Up to (e*d - 1)//32 is safe, because 32 divides e*d - 1 in this particular case
a = pow(2, (e*d - 1)//4, N)

# Should still have pow(a,2,N) = 1
pow(a, 2, N)

1

# Is a a nontrivial square root of unity
a

1

a = pow(2, (e*d - 1)//8, N)

pow(a, 2, N)

1

a

1

a = pow(2, (e*d - 1)//16, N)

pow(a, 2, N)

1

a

930574182607604323320953391297898416578967684490484759376547

N-1

945579382313214135470583525960206135776873895012524267916946

\(a \not\equiv \pm 1 \bmod N\), so it’s a nontrivial square root of unity. Good! Can use \(a\) to factor \(N\).

gcd(a+1, N)

775420272912138361926536898569

gcd(a-1, N)

1219441140946744671516135755963

p

1219441140946744671516135755963

q

775420272912138361926536898569

This worked!

There are two possible failures:

  1. we get 1 until the exponent becomes odd.

  2. we get -1 at some point (then we need to stop)

If one of those failures happens, then we should change the base x.

a2 = pow(3, (e*d-1)//8, N)
a2

930574182607604323320953391297898416578967684490484759376547

N

945579382313214135470583525960206135776873895012524267916947

# The base x = 3 also worked
gcd(a2-1, N)

1219441140946744671516135755963
Created in deepnote.com Created in Deepnote