Description:
Tears dripped from my face as I stood over the bathroom sink. Exposed again! The tears melted into thoughts, and an idea formed in my head. This will surely keep my secrets safe, once and for all. I crept back to my computer and began to type.
We are given a relatively long python script implementing RSA encryption, together with a public key and an encrypted file. They use a custom key format which is saved using the pickle module:
class Key:
PRIVATE_INFO = ['P', 'Q', 'D', 'DmP1', 'DmQ1']
def __init__(self, **kwargs):
for k, v in kwargs.items():
setattr(self, k, v)
assert self.bits % 8 == 0
def ispub(self):
return all(not hasattr(self, key) for key in self.PRIVATE_INFO)
def ispriv(self):
return all(hasattr(self, key) for key in self.PRIVATE_INFO)
def pub(self):
p = deepcopy(self)
for key in self.PRIVATE_INFO:
if hasattr(p, key):
delattr(p, key)
return p
def priv(self):
raise NotImplementedError()
def genkey(bits):
assert bits % 2 == 0
while True:
p = genprime(bits // 2)
q = genprime(bits // 2)
e = 65537
d, _, g = egcd(e, (p - 1) * (q - 1))
if g != 1: continue
iQmP, iPmQ, _ = egcd(q, p)
return Key(
N=p * q, P=p, Q=q, E=e, D=d % ((p - 1) * (q - 1)), DmP1=d % (p - 1), DmQ1=d % (q - 1),
iQmP=iQmP % p, iPmQ=iPmQ % q, bits=bits,
)
Notice that the values iPmQ and iQmP are not removed when constructing the public key.
Let us call these values $a$ and $b$ in the following.
If $a’, b’=egcd(p, q)$, then $a’p+b’q=gcd(p,q)$ by Bézout’s identity.
Hence,
\[
\quad (a+iq)p + (b+jp)q = 1\nl
\Rightarrow ap+bq+(i+j)pq = 1\nl
\Rightarrow ap+bq=1+zn=:c
\]
for small values $i,j,z\in \mathbb Z$.
Let $x, y = egcd(a, b)$. Since $gcd(a, b)=1$ (in our case), we have
\[ \quad ap+bq=1+zn=c\nl \quad ax+by=1\nl \Rightarrow a(p-xc)+b(q-yc) = 0\qquad \text{(subtract the second equation $c$ times from the first)}\nl \Rightarrow a(p-xc) = b(yc-q)\nl \Rightarrow (q-yc) \equiv 0 \mod a\nl \Rightarrow q-yc=ka \]
We can expect $q/a$ to be small. Hence, $k\approx -yc/a$. Then, $q=ka+yc$.
a = k.iPmQ
b = k.iQmP
n = k.N
x, y, _ = egcd(a, b)
for z in range(-10, 10):
c = 1 + z*n
for k in range(-y*c//a-10, -y*c//a+10):
q = k*a + y*c
if n % q == 0:
print(q, n//q)
/upb/hack e.V.
IBAN: DE91472601218328783500
BIC: DGPBDE3MXXX
Wir sind ein eingetragener, gemeinnütziger Verein. Für eine Spendenquittung wenden Sie sich bitte an: [email protected]
Unsere digitale Spendenquittung können Sie mit dem folgenden Zertifikat verifizieren: Zertifikat