While in the process of discovering the gcd of two numbers, a and b, it's possible, at the same time, to extract two additional integers, m and n, such that:
$$ a\ m + b\ n = gcd(a, b) $$m or n will be negative.
The idea is two multiples of a and b (say m and n) will get them within one GCD of one another, i.e. the GCD brick will divide both a and b bricks (by definition), so there's a way to stack a and b side by side such that the only difference in height between the two stacks is their greatest in-common divisor.
def gcd(a, b):
"""
Recursive version of gcd
"""
if b == 0: # no remainder, b (now a) was gcd
return a
return gcd(b, a%b)
gcd(20, 170)
10
def xgcd(a, b):
"""
Extended Euclidean Alg.
take positive integers a, b as input, and return
a triple (g, x, y), such that ax + by = g = gcd(a, b).
"""
x0, x1, y0, y1 = 1, 0, 0, 1
while b != 0:
q, a, b = a // b, b, a % b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0
a, b = 100, 85
gcd_, m, n = xgcd(a, b)
gcd_, m, n
(5, 6, -7)
The GCD is the leftmost number, then come m and n such that:
a * m + b * n == gcd(a, b)
True
a, b = 14, 17
gcd_, m, n = xgcd(a, b)
gcd_, m, n
(1, -6, 5)
a * m + b * n == gcd(a, b)
True
def invmod(a, N):
"""
What is the multiplicative inverse of a, inv_a,
such that a * inv_a = 1 mod N.
"""
return xgcd(a, N)[1] % N # inv_a (gcd is 1, a * x0 + N * x1 = 1)
invmod(14, 17) # what number times 14, mod 17, is 1?
11
(14 * 11) % 17
1
invmod(3, 17)
6
(3 * 6) % 17
1
Lets see where invmod
fits in to the RSA algorithm.
p = 593
q = 601
N = p * q # public key comprised of two primes
N
356393
phiN = (p-1)*(q-1) # phi(ab)=phi(a)phi(b)
phiN
355200
e = 17
d = invmod(e, phiN) # what is e's multiplicative inverse mod phiN?
d
167153
e * d
2841601
(e*d) % phiN
1
But what size public keys are we really talking about?
RSA232 = \
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689
p = 4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589
q = 3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901
if RSA232 == p*q:
print("Check!")
Check!
hex(RSA232)[2:]
'2f68a7dece4554b9f829dd67abf99118633a653e8c7b56f8f86820570cbd9399915e2c5d0c790156bda44c0632e8371f14161b55abb9066263e8846980abc14978f29380efd9a432d5fc7d139e1ab27bb6197962f18d672a0cc7e108337b051'
N = RSA232
phiN = (p-1)*(q-1) # 𝜙(a * b) = 𝜙(a) * 𝜙(b) if a, b coprime, 𝜙(p) = p-1 if p prime
e = 17
d = invmod(e, phiN) # what d, multiplied by e, will be 1 mod phiN?
d # secret key (stays safe with the public key holder)
10570289175259451019362428499748968327275036357654470629934658138548074388436171137349042498746265150135797567176423956018503248984269945430046922024466863299558267938031191018569191870150828300405595010449202998525804603031798353
m = int(bytes.hex(b'attack at dawn!'), 16)
c = pow(m, e, N) # encrypt using N
outcome = pow(c, d, N) # decrypt using d
bytes.fromhex(hex(outcome)[2:])
b'attack at dawn!'