xct's notes
Search…
RSA

RSA Encrypt & Decrypt with Sage

1
#!/usr/bin/env sage
2
3
import sys
4
from sage.all import *
5
6
m = 12
7
8
p = 17
9
q = 23
10
e = 65537
11
12
n = p * q
13
pn = (p-1)*(q-1)
14
d = inverse_mod(e, pn)
15
16
c = power_mod(m,e,n)
17
print(c)
18
19
m = power_mod(c,d,n)
20
print(m)
Copied!

Euler Totient with Sage

1
#!/usr/bin/env sage
2
3
import sys
4
from sage.all import *
5
6
p = 857504083339712752489993810777
7
q = 1029224947942998075080348647219
8
9
print(euler_phi(p*q))
Copied!

Common Modulus

You have 2 keys (with common n, but different e) and 2 ciphertexts. Do:
1
gcd, aa, bb = extended_gcd(a.e, b.e)
2
3
if aa < 0:
4
m1 = modinv(m1, a.n)
5
aa = -(aa)
6
7
if bb < 0:
8
m2 = modinv(m2, b.n)
9
bb = -(bb)
10
11
m = (pow(m1, aa, a.n) * pow(m2, bb, b.n))%a.n
Copied!

Factor N when 2 close Primes are used

1
from sage.all import *
2
3
n = ...
4
5
a = ceil(sqrt(n))
6
b = (a*a) - n
7
while not b.is_square():
8
a = a + 1
9
b = (a * a) - n
10
11
p = a - sqrt(b)
12
q = a + sqrt(b)
Copied!
Last modified 7mo ago