红明谷2021-ezCRT

Posted on Edited on In , Views: Symbols count in article: 13k Reading time ≈ 12 mins.

 

考点

  • Common Private Exponent

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
import gmpy2
from random import shuffle

flag = b"flag is here"


def shuffle_flag(s):
    str_list = list(s)
    shuffle(str_list)
    return ''.join(str_list)


nl = []
el = []
count = 0
while count != 5:
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1) * (q - 1)
    d = gmpy2.next_prime(bytes_to_long(flag))
    e = gmpy2.invert(d, phi)
    nl.append(n)
    el.append(int(e))
    count += 1

print(nl)
print(el)

cl = []
flag = shuffle_flag(flag.decode()).encode()
for i in range(len(nl)):
    cl.append(pow(bytes_to_long(flag), el[i], nl[i]))
print(cl)

已经五组$n,e,c$，他们使用相同私钥$d$，且私钥较小

  • Common Private Exponent的使用条件

    $d \lt N_i^{\delta_i}，\delta_i \lt \cfrac{1}{2}-\cfrac{1}{2(i+1)}-\log_{N_i}{6}$

  • 推导

    因为
    $$
    \begin{cases}
    e_1d=1+k_1\varphi(n_1)\\
    e_2d=1+k_2\varphi(n_2)\\
    e_3d=1+k_3\varphi(n_3)\\
    e_4d=1+k_4\varphi(n_4)\\
    e_5d=1+k_5\varphi(n_5)
    \end{cases}\notag
    $$
    设未知数为$k_i$，尝试减小其他未知数个数

    由于$\varphi(n_1)=n_1-(p_i+q_i)+1$，令$s_i=-(p_i+q_i)+1$
    $$
    \begin{cases}
    e_1d-k_1n_1=k_1s_1+1\\
    e_2d-k_2n_2=k_2s_2+1\\
    e_3d-k_3n_3=k_3s_3+1\\
    e_4d-k_4n_4=k_4s_4+1\\
    e_5d-k_5n_5=k_5s_5+1
    \end{cases}\notag
    $$
    构造矩阵乘法
    $$
    AB=C\notag
    $$
    其中，

    $A=(d,k_1,k_2,k_3,k_4,k_5)$

    $B=\begin{bmatrix} M & e_1 & e_2 &e_3&e_4&e_5\\0 & -n_1 & 0&0&0&0\\0 & 0 &-n_2&0&0&0\\0&0&0&-n_3&0&0\\0&0&0&0&-n_4&0\\0&0&0&0&0&-n_5\end{bmatrix}$

    $C=(dM,e_1d-k_1n_1,e_2d-k_2n_2,e_3d-k_3n_3,e_4d-k_4n_4,e_5d-k_5n_5)$

    $M=\sqrt {n_1}$，是为了调整范数。对矩阵$B$格基规约得到$C$，第一位除以$M$就是私钥$d$了；解出flag

求d脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert, sqrt
nl = [92568419674731290088321621356482160506897805615722568594108449347104924357404183476911642777855820991398881156764068184840768873749718093598712551142529474514837161712525386555067489900887826033760157015587905876891826276883359425048106383489316555600680137377034136599761900203863336332834524981581608546277, 156396473818563541024482014372866929605198443382524196879362284224099117401220679011156723462510565131555949471059964179767945960498473012008220045105490122503438703770112687917922899337041421537937431868908340506324082719417747902320117904166584374628828367801012533926776313544525573302674702867896838756349, 158394833243620345170313957479796081390446308753163267294427471181012679879060921676287361174926310080500003540773261012005682050743188110335872216992843352902160171999286576526304619756655278142788064189969927027027650043645613441449926633380809295720977302961310978360575684689811662689798196832145977450067, 160088237013152996062303719345275590040820298863729670660621544625451638541931139026114480452748397901155923890465415946150076272684251867169893163248736673419035618274961179288085209456220719404244194802327491684233804878013160262798831738441790443743813368173495029170393018727204042599457829167334217403039, 176125361422384852665447804150030174008849487020728296169340093618559367127086381778331613043595010796295772394708222184703701230685609172767761426620379001062695169120599393984950488304290958534830276649464003949555105491117656796777657620812669612752464591728873199832200616338112460100967288829163217253937]
el = [69312028009355287369151190914681978515224902099126626288106202481561083869512381976466800912049172557479956400189281179789850182367192324370292880508005951892909864237831856642160554901550928757105750738313195248541515727624216048436593804176317465366380022764459799506858495981817822670957526705611211712923, 75652848678989239962391202584125835503829570694373189157636155436633908234362973839251550542975725789188895010096917574118924190081886365041870173203566890015476761857546914959928731140619341634983144909962106759048918025248827973161384045263311189477657141886093632791593341193393085433749877270828641736687, 33787880341418355427411601538315129862488529656310145182009801227014512555036822623215545927750632031483856865027938518144081751233475248361490189179988637342429805607352670543555743822390555949569061340741015073482051059972283793490798701339277926430357560613555427570475360496737455291914090967005368044847, 45894271603047945281790624112313938740541711331584775481261776728213544262108835859642003140814571796838418889270625806159755478669858113687476417240730385707171289922064965084283027730393146219788228689778873266618663473231744646293406030907691363263939114550226424730102211751706087680590823466426973879111, 39462780066564051085365889083337472288277223628014907704844994419242541623368920096395581667207909872944692627394665038729398405841875334128211337544205143876652949004817962123951132753801707134333132359039376283331685997619531570270269964807335633423631078057345827010794671894948828680193958561375351954627]
cl = [706565317398633346290694952311166623770389747503953970254889622211015097472765489676349936599997109100148837713409666075736711752497174928509516666210124850782396573268200919345005742905131769799719677758163730270857245509037860252700476102090438501579886321486095767737006847692632649652528793934802014895, 39976293505792731417500342473259466413746324373570160856607039564687056797068114044891309890160001547746290678089875953230720229396293686037539133378586045964793387433679304899158546834837314101138069400994334720071006048815998660691472991971598192116289517127819703723844842002711298154106615035755646791235, 82622936948791971063481195310587447614375265630407688161651173440160941964839173273115526802240672776681580169092371677673709037579318090622040018030730165371997331146171751228791524747622285256591779419274845659567001522182995468819720594650389854677582186770321424062935881407083956991646633760500152137305, 47924672523033740219454774309397006543851002473271747603676349322670782245519637286314088457132590816165876451615235937683074852920250584155682791595116359054889940842281324709426616771765312825842634237678243213350551342690870568516232078792788925700389762945955053433276153136302757700081859531596237286407, 157462720644970256050843434459828247139256140406409429896418317109064365936294939244159292550184482469972819258184119865598346921909220060266145241164734603316978286567811044606538176157224828857158099074286931716459626013079677895357212211176535500327064375073662684801175545519382470886239209020257096407424]
M = int(sqrt(nl[0]))
A = matrix([[M, el[0], el[1], el[2], el[3], el[4]],
           [0, -nl[0], 0, 0, 0, 0],
           [0, 0, -nl[1], 0, 0, 0],
           [0, 0, 0, -nl[2], 0, 0],
           [0, 0, 0, 0, -nl[3], 0],
           [0, 0, 0, 0, 0, -nl[4]]])
C = A.LLL()
d = C[0][0] // M
print(d)
# 4035685915436099980994650889948556572401301700215759631583373002944008951077734389446917516925581134450058777751810063
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes, bytes_to_long
from gmpy2 import invert, next_prime
flag = b"flag is here"
d = 4035685915436099980994650889948556572401301700215759631583373002944008951077734389446917516925581134450058777751810063
nl = [92568419674731290088321621356482160506897805615722568594108449347104924357404183476911642777855820991398881156764068184840768873749718093598712551142529474514837161712525386555067489900887826033760157015587905876891826276883359425048106383489316555600680137377034136599761900203863336332834524981581608546277, 156396473818563541024482014372866929605198443382524196879362284224099117401220679011156723462510565131555949471059964179767945960498473012008220045105490122503438703770112687917922899337041421537937431868908340506324082719417747902320117904166584374628828367801012533926776313544525573302674702867896838756349, 158394833243620345170313957479796081390446308753163267294427471181012679879060921676287361174926310080500003540773261012005682050743188110335872216992843352902160171999286576526304619756655278142788064189969927027027650043645613441449926633380809295720977302961310978360575684689811662689798196832145977450067, 160088237013152996062303719345275590040820298863729670660621544625451638541931139026114480452748397901155923890465415946150076272684251867169893163248736673419035618274961179288085209456220719404244194802327491684233804878013160262798831738441790443743813368173495029170393018727204042599457829167334217403039, 176125361422384852665447804150030174008849487020728296169340093618559367127086381778331613043595010796295772394708222184703701230685609172767761426620379001062695169120599393984950488304290958534830276649464003949555105491117656796777657620812669612752464591728873199832200616338112460100967288829163217253937]
el = [69312028009355287369151190914681978515224902099126626288106202481561083869512381976466800912049172557479956400189281179789850182367192324370292880508005951892909864237831856642160554901550928757105750738313195248541515727624216048436593804176317465366380022764459799506858495981817822670957526705611211712923, 75652848678989239962391202584125835503829570694373189157636155436633908234362973839251550542975725789188895010096917574118924190081886365041870173203566890015476761857546914959928731140619341634983144909962106759048918025248827973161384045263311189477657141886093632791593341193393085433749877270828641736687, 33787880341418355427411601538315129862488529656310145182009801227014512555036822623215545927750632031483856865027938518144081751233475248361490189179988637342429805607352670543555743822390555949569061340741015073482051059972283793490798701339277926430357560613555427570475360496737455291914090967005368044847, 45894271603047945281790624112313938740541711331584775481261776728213544262108835859642003140814571796838418889270625806159755478669858113687476417240730385707171289922064965084283027730393146219788228689778873266618663473231744646293406030907691363263939114550226424730102211751706087680590823466426973879111, 39462780066564051085365889083337472288277223628014907704844994419242541623368920096395581667207909872944692627394665038729398405841875334128211337544205143876652949004817962123951132753801707134333132359039376283331685997619531570270269964807335633423631078057345827010794671894948828680193958561375351954627]
cl = [706565317398633346290694952311166623770389747503953970254889622211015097472765489676349936599997109100148837713409666075736711752497174928509516666210124850782396573268200919345005742905131769799719677758163730270857245509037860252700476102090438501579886321486095767737006847692632649652528793934802014895, 39976293505792731417500342473259466413746324373570160856607039564687056797068114044891309890160001547746290678089875953230720229396293686037539133378586045964793387433679304899158546834837314101138069400994334720071006048815998660691472991971598192116289517127819703723844842002711298154106615035755646791235, 82622936948791971063481195310587447614375265630407688161651173440160941964839173273115526802240672776681580169092371677673709037579318090622040018030730165371997331146171751228791524747622285256591779419274845659567001522182995468819720594650389854677582186770321424062935881407083956991646633760500152137305, 47924672523033740219454774309397006543851002473271747603676349322670782245519637286314088457132590816165876451615235937683074852920250584155682791595116359054889940842281324709426616771765312825842634237678243213350551342690870568516232078792788925700389762945955053433276153136302757700081859531596237286407, 157462720644970256050843434459828247139256140406409429896418317109064365936294939244159292550184482469972819258184119865598346921909220060266145241164734603316978286567811044606538176157224828857158099074286931716459626013079677895357212211176535500327064375073662684801175545519382470886239209020257096407424]
N = 1
M = 0
A = [0 for i in range(5)]
B = [0 for j in range(5)]
ml = [0 for k in range(5)]
for i in nl:
    N *= i
for i in range(5):
    A[i] = N // nl[i]
    B[i] = invert(A[i], nl[i])
    ml[i] = int(pow(cl[i], d, nl[i]))
    M += ml[i]*A[i]*B[i]
print(long_to_bytes(M % N))

跑出来是这个

1
8b3i7a4af3fb3{adcb-56a-6nd78a-gb89g-42p}efd33l9d2

回看了下题目，因为

1
d = gmpy2.next_prime(bytes_to_long(flag))

所以知道了d就知道了flag

对格基规约的小理解

对于
$$
AB=C\notag
$$
其中

$A=
\begin{bmatrix}
d & k_1 & k_2 & k_3 & k_4 & k_5\\
d & k_1 & k_2 & k_3 & k_4 & k_5\\
d & k_1 & k_2 & k_3 & k_4 & k_5\\
d & k_1 & k_2 & k_3 & k_4 & k_5\\
d & k_1 & k_2 & k_3 & k_4 & k_5\\
d & k_1 & k_2 & k_3 & k_4 & k_5
\end{bmatrix}\notag$

$B=\begin{bmatrix} M & e_1 & e_2 &e_3&e_4&e_5\\0 & -n_1 & 0&0&0&0\\0 & 0 &-n_2&0&0&0\\0&0&0&-n_3&0&0\\0&0&0&0&-n_4&0\\0&0&0&0&0&-n_5\end{bmatrix}$

$C=
\begin{bmatrix}
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5\\
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5\\
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5\\
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5\\
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5\\
dM & e_1d-k_1n_1 & e_2d-k_2n_2 & e_3d-k_3n_3 & e_4d-k_4n_4 & e_5d-k_5n_5
\end{bmatrix}\notag$

在线性代数中，可以将矩阵看作线性变换，$AB=C$意味着，$B$可以通过$A$所代表的线性变换变成$C$

通过构造使得满足一些条件，可以证明$C$是$B$的最短向量，对$B$进行格基规约就能得到$C$

也许这就是格基规约的原理

Reference

  1. Lazzaro-RSA-Common Private Exponent（共私钥指数攻击，d相同）
  2. Lattice Based Attack on Common Private Exponent RSA