Three Ravens (RSA)
{"author" : ["ret2basic"]}

Challenge

There were three ravens sat on a tree, Downe a downe, hay downe, a downe, They were as black as they might be.
Attachment:

Code Review

1
#!/usr/bin/python
2
3
from Crypto.Util.number import *
4
from flag import flag
5
6
def keygen(nbit):
7
while True:
8
p, q, r = [getPrime(nbit) for _ in range(3)]
9
if isPrime(p + q + r):
10
pubkey = (p * q * r, p + q + r)
11
privkey = (p, q, r)
12
return pubkey, privkey
13
14
def encrypt(msg, pubkey):
15
enc = pow(bytes_to_long(msg.encode('utf-8')), 0x10001, pubkey[0] * pubkey[1])
16
return enc
17
18
nbit = 512
19
pubkey, _ = keygen(nbit)
20
print('pubkey =', pubkey)
21
22
enc = encrypt(flag, pubkey)
23
print('enc =', enc)
Copied!
This is a modified RSA cryptosystem with
e=65537e = 65537
and
N=(pqr)(p+q+r)N = (pqr)(p+q+r)
, where
pp
,
qq
, and
rr
are three 512-bit randomly generated primes.

Solution

Since
NN
is large, we won't be able to compute
ϕ(N)\phi(N)
directly. Instead of computing
ϕ(N)\phi(N)
, the idea here is to "reduce"
NN
to some reasonably small
NN'
and compute
ϕ(N)\phi(N')
. In fact, I claim that computing
ϕ(N)\phi(N)
is equivalent to computing
ϕ(p+q+r)\phi(p+q+r)
with an assumption:
p+q+rp+q+r
is prime.
Proof:
cmemodNcmemod[(pqr)(p+q+r)]cme+k[(pqr)(p+q+r)]cme+(kpqr)(p+q+r)cmemod(p+q+r)c \equiv m^e \bmod N \\ c \equiv m^e \bmod [(pqr)(p+q+r)] \\ c \equiv m^e + k \cdot [(pqr)(p+q+r)]\\ c \equiv m^e + (kpqr)(p+q+r) \\ c \equiv m^e \bmod (p+q+r)
where
kZk \in \mathbb{Z}
. Let
N=p+q+rN' = p+q+r
, then
ϕ(N)=p+q+r1\phi(N) = p+q+r-1
since we assumed that
p+q+rp+q+r
is prime. Now we can easily decrypt the ciphertext since
p+q+rp+q+r
is known. Using this method, we will get the flag, hence the assumption is true.

Implementation

1
#!/usr/bin/env python3
2
from Crypto.Util.number import inverse, long_to_bytes
3
4
#--------Data--------#
5
6
pubkey = (1118073551150541760383506765868334289095849217207383428775992128374826037924363098550311115755885268424829560194236035782255428423619054826556807583363177501160213010458887123857150164238253637312857212126083296001975671629067724687807682085295986049189947830021121209617616433866087257702543240938795900959368763108186758449391390546819577861156371516299606594152091361928029030465815445679749601118940372981318726596366101388122993777320367839724909505255914071, 31678428119854378475039974072165136708037257624045332601158556362844808093636775192373992510841508137996049429030654845564354209680913299308777477807442821)
7
e = 65537
8
c = 8218052282226011897229703907763521214054254785275511886476861328067117492183790700782505297513098158712472588720489709882417825444704582655690684754154241671286925464578318013917918101067812646322286246947457171618728341255012035871158497984838460855373774074443992317662217415756100649174050915168424995132578902663081333332801110559150194633626102240977726402690504746072115659275869737559251377608054255462124427296423897051386235407536790844019875359350402011464166599355173568372087784974017638074052120442860329810932290582796092736141970287892079554841717950791910180281001178448060567492540466675577782909214
9
10
#--------RSA with reducible modulus--------#
11
12
p_plus_q_plus_r = pubkey[1]
13
14
phi = p_plus_q_plus_r - 1
15
d = inverse(e, phi)
16
m = pow(c, d, p_plus_q_plus_r)
17
flag = long_to_bytes(m).decode()
18
19
print(flag)
Copied!
Last modified 2mo ago