Model (RSA)
{"author" : ["ret2basic"]}

Challenge

The encryption validation thread model is invalid!
nc 04.cr.yp.toc.tf 8001
Menu
There are 5 options:
    1.
    Get function genkey()
    2.
    Get function encrypt()
    3.
    Get ciphertext c
    4.
    Get public key (e, n)
    5.
    Encryption oracle

Code Review

1
def genkey(nbit):
2
while True:
3
p, q = getPrime(nbit), getPrime(nbit)
4
if gcd((p-1) // 2, (q-1) // 2) == 1:
5
P, Q = (q-1) // 2, (p-1) // 2
6
r = inverse(Q, P)
7
e = 2 * r * Q - 1
8
return(p, q, e)
9
10
def encrypt(msg, pubkey):
11
e, n = pubkey
12
return pow(bytes_to_long(msg), e, n)
Copied!

Solution

Simplify
ee
:
e=2rQ1e=(21)modPe=1modPe=1+kPe = 2 \cdot r \cdot Q - 1\\ e = (2 - 1) \bmod P\\ e = 1 \bmod P\\ e = 1 + k \cdot P
for some
kZk \in \mathbb{Z}
. Let the modulus
nn
be
n=pqn = p \cdot q
. Now consider
cc
:
cmemodncm1+kPmodncmmkPmodncmmk(q1)2modnc \equiv m^e \bmod n\\ c \equiv m^{1 + k \cdot P} \bmod n\\ c \equiv m \cdot m^{k \cdot P} \bmod n\\ c \equiv m \cdot m^{\frac{k(q-1)}{2}} \bmod n\\
Since
n=pqn = p \cdot q
, here
cmmk(q1)2modnc \equiv m \cdot m^{\frac{k(q-1)}{2}} \bmod n
is just
cmmk(q1)2modqc \equiv m \cdot m^{\frac{k(q-1)}{2}} \bmod q
. Continue:
cm(mq1)k2modqc \equiv m \cdot (m^{q-1})^{\frac{k}{2}} \bmod q
By Fermat Little Theorem, we have:
cm1k2modqcm1k2modqcmmodqcm0modqcm=kqc \equiv m \cdot 1^{\frac{k}{2}} \bmod q\\ c \equiv m \cdot 1^{\frac{k}{2}} \bmod q\\ c \equiv m \bmod q\\ c - m \equiv 0 \bmod q\\ c - m = k' \cdot q
where
kZk' \in \mathbb{Z}
. Since
cmc - m
is a multiple of
qq
and
nn
is a multiple of
qq
, we know that
qq
is the GCD of
cmc - m
and
nn
. Once we compute
qq
, we are able to recover the flag.

Implementation

solve.sage
1
#!/usr/bin/env sage
2
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
3
4
#--------Data--------#
5
6
n = 17790613564907955318126717576181316624843451677921227941389832111093895513875496295594784102148835715126789396535470416868485674231839509486983792844881941097589192520877472968227711640216343330193184235164710328845507199362646489303138765492026284976828397217700058854699501312701069031398507487060508966602815218264215778115331187180105972920333780067280854048113094622799996118383376340217782122945586262887450863620856214375258659362300743471229410735400189992359220551961441580630740022857304514895745174813529758766758733506538696933950282130984955594881517339093338779101106466633380921338845195921235252323721
7
encrypted_flag = 8216344743331409189205831776342200252705923796193752552649425282859227400617284746437075756157249953578189229459392338128783031841882560801175367779263048253787547952450480816724222285583987363793884961526545550108790689158473753461378651141379053427506957702375732452598640804768960184186521954448243004125900395894265450073650101942224629389391631821735998886688813393717718376391743836798122485350719355567861201466641767009303179260141365766023680788250688524528992952859061172438083227729190577738108854783536925967748199734513738782142055609101950770816942854252284355975365351013803601963990179403849614198536
8
9
# Feed a plaintext "0" to the encryption oracle and record the output
10
m = bytes_to_long(b"0")
11
c = 8131881080215090371487466406674376044247120209816118806949066423689730735519795472927218783473464525260814227606067990363574576048132004742403517775620572793232598693334765641758830271460405790617624271060522834683042735967050146871067065889288923913486919193720360254923458500009885281654478144592942337767754315130844294762755237864506689552987776560881357285727629827190391683150994461127468196118126587159811046890420456603820675085450111755868116701855834309297184745623927049652098555126342100576188575279791066071616897443075423425299542959405192350563251777193668273523389978129359003036691597884885020756981
12
13
#--------Find q--------#
14
15
# c - m is a multiple of q and n is a multiple of q
16
# Hence q is the gcd of c - m and n
17
q = gcd(c - m, n)
18
19
#--------Recover flag--------#
20
21
p = n // q
22
P, Q = (q - 1) // 2, (p - 1) // 2
23
r = inverse(Q, P)
24
e = 2 * r * Q - 1
25
phi = (p - 1) * (q - 1)
26
d = inverse(e, phi)
27
m = pow(encrypted_flag, d, n)
28
flag = long_to_bytes(m).decode()
29
30
print(flag)
Copied!
Last modified 2mo ago