alice_bob_dave

Common factor in RSA modulus.

Problem

Alice and Bob are sending their flags to Dave. But sadly Dave lost the modulus :( Try to retrieve the flag!

Solution

We are given the following source code:

from Crypto.Util.number import *
from secret import msg_a,msg_b

e=65537
p,q,r=[getStrongPrime(1024,e) for _ in range(3)]
pt_a=bytes_to_long(msg_a)
pt_b=bytes_to_long(msg_b)

n_a=p*q
n_b=p*r
phin_a=(p-1)*(q-1)
phin_b=(p-1)*(r-1)
d_a=inverse(e,phin_a)
d_b=inverse(e,phin_b)

ct_a=pow(pt_a,e,n_a)
ct_b=pow(pt_b,e,n_b)

print(f"{ct_a=}\n{ct_b=}\n{d_a=}\n{d_b=}\n{e=}")

And the output:

ct_a=1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b=11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a=12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b=15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e=65537

Notice the way that the modulus is chosen. Three primes (p, q, and r) are chosen. The first modulus is $n_a=p\times q$ , and the second is $n_b=p\times r$.

Our first observation should be that both moduli share $p$ as a common factor.

Recall that in RSA, for $n=p\times q$, the private exponent$d$ is chosen such that

$$ed\equiv1\pmod{\text{lcm}(p-1,q-1)}$$

i.e. for some$k\in\mathbb{Z}$,

$$ed=1+k(p-1)(q-1)$$

For $n_a=p\times q$ and $n_b=p\times r$,

$$ed_a-1=k_a(p-1)(q-1) \newline ed_b-1=k_b(p-1)(r-1)$$

Since we are given $e$, $d_a$ and $d_b$, we know the values of $k_a(p-1)(q-1)$ and $k_b(p-1)(r-1)$. It is trivial to deduce that the greatest common divisor (GCD) between these two values is a multiple of $(p-1)$. Let's call this $\alpha(p-1)$.

We can write the following code to obtain $\alpha(p-1)$:

from decimal import *
getcontext().prec = 1000

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
de_a = d_a * e
de_b = d_b * e
p_multiple = Decimal(gcd(de_a - 1, de_b - 1))

We could then iteratively test for the value of $\alpha$ by asserting that $p$ must be prime.

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d//2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

for i in range(2, 100):
    p = Decimal(p_multiple) / Decimal(i) + 1
    if isPrime(int(p)):
        print('p =', p)
        break

After finding $p$, we simply note that

$$\frac{ed_a-1}{p-1}=k_a(q-1)$$

and use a similar method to find $q$. Then, we attempt to decode the ciphertext:

$$p_a=(c_a)^d\mod{n}$$

q_multiple = Decimal(de_a - 1) / (p - 1)

for i in range(2, 100000):
    q = Decimal(q_multiple) / Decimal(i) + 1
    if isPrime(int(q)):
        m = pow(int(ct_a), int(d_a), int(p) * int(q))
        msg = long_to_bytes(m)
        try:
            print(msg.decode())
            break
        except:
            continue

The method to find $r$ and decode the second part of the flag is exactly the same.

r_multiple = Decimal(de_b - 1) / (p - 1)
for i in range(2, 100000):
    r = Decimal(r_multiple) / Decimal(i) + 1
    if isPrime(int(r)):
        m = pow(int(ct_b), int(d_b), int(p) * int(r))
        msg = long_to_bytes(m)
        try:
            print(msg.decode())
            break
        except:
            continue

Here's the output: