ACSC 2021 | Two Rabin - crypto-writeup-public

#acsc2021

import random
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
B = getStrongPrime(512)

m = flag[0:len(flag)//2]
print("flag1_len =",len(m))

m1 = bytes_to_long(m)
m2 = bytes_to_long(pad(m,128))

assert m1 < n
assert m2 < n

c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n

print("n =",n)
print("B =",B)
print("c1 =",c1)
print("c2 =",c2)

# Harder!

m = flag[len(flag)//2:]
print("flag2_len =",len(m))

m1 = bytes_to_long(m)
m1 <<= ( (128-len(m))*8 )
m1 += random.SystemRandom().getrandbits( (128-len(m))*8 )

m2 = bytes_to_long(m)
m2 <<= ( (128-len(m))*8 )
m2 += random.SystemRandom().getrandbits( (128-len(m))*8 )

assert m1 < n
assert m2 < n

c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n

print("hard_c1 =",c1)
print("hard_c2 =",c2)

RabinCryptosystemが2つある

前半パートは

$c_1 = m_1^2 + m_1B \mod N$

$c_2 = m_2^2 + m_2B \mod N$

かつ $m_2 = m_1 * 2^x + \alpha$ で、 $x, \alpha$ 既知なので実質変数一つ

適当にFranklin-Reiter Related Message Attackをやって解く。

PR.<x> = PolynomialRing(Zmod(n))
l = 128 - 98
y = x * 2**(l*8) + int.from_bytes(bytes([l]) * l, "big")

f1 = x*x + x*B - c1
f2 = y*y + y*B - c2

def pgcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

flag1 = bytes.fromhex(hex(-pgcd(f1, f2).coefficients()[0])[2:])
print(flag1)

後半パートは

$c_1 = x^2 + xB \mod N$

$c_2 = y^2 + yB \mod N$

で $x = 2^km + \alpha, y = 2^km + \alpha$ 、で今度は $\alpha, \beta$ は完全な乱数

しかしこれも $\beta = \alpha + r$ と置くことで1変数 + 小さい誤差の式にできる。

resultantをつかって変数を式から追い出しながら、 $r$ を求める方針で解ける

Coppersmith's Short Pad Attack

PR.<x, y> = PolynomialRing(Zmod(n))
PZ.<xz, yz> = PolynomialRing(Zmod(n))


f1 = x*(x + B) - hard_c1
f2 = (x+y)*(x + y + B) - hard_c2

q1 = f1.change_ring(PZ)
q2 = f2.change_ring(PZ)

PN.<xn> = PolynomialRing(Zmod(n))
f = q1.resultant(q2).univariate_polynomial().change_ring(PN).subs(y=xn)
diffs = f.small_roots(X=2**(l*8), beta=1, epsilon=0.025)

PR.<x> = PolynomialRing(Zmod(n))
for d in diffs:
    f1 = x*(x + B) - hard_c1
    f2 = (x+d)*(x + d + B) - hard_c2

    flag2 = bytes.fromhex(hex(-pgcd(f1, f2).coefficients()[0])[2:])
    print(flag2)