密码学

factor

[Attack 7.2] Cryptanalysis of RSA and It's Variants

和书上的$Common \ Private \ Exponent \ Attack$差不了多少
e是对 $(p + 1)(q + 1)$ 取的,所以LLL之后解出来,b的第二维应该是 $1+k_1s1$,

$$
k_1 = \frac{e_1d - (1+K_1)}{N_1}
$$

然后

$$
p+q = \frac{d*e_1 - 1}{k_1}
$$

之后选择了二分搜索把 $p$ 找出来,解方程也可以

N1 = 115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177
N2 = 53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229
e1 = 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611
e2 = 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003

delta = 300./1024
M = int(sqrt(N2))
B = Matrix(ZZ, [ [M,  e1, e2],
                 [0, -N1,  0],
                 [0,  0, -N2]])
L = B.LLL()
d = int(L[0][0] / M)

v1 = int(L[0][1])
k1 = (e1 * d - v1) // N1
_sum = (d*e1 - 1) // k1 - N1 - 1
left, right = 1, _sum

while left <= right:
    mid = (left + right) >> 1
    if (_sum - mid) * mid > N1:
        right = mid - 1
    elif (_sum - mid) * mid < N1:
        left = mid + 1
    else:
        p, q = mid, _sum - mid
        break

c1 = 51861394323132582263685584977796608641129485967610029542263453128833142621927008505594685713111162217651119546991411861320042282788909858323941435593508384080858965324662410947546608051702238057613339996124961723578887443100478753831786550701578678090466528863014222331341645240511640398819027209200809466160

m = pow(c1, inverse_mod(e1, (p - 1)*(q - 1)), N1)
print(bytes.fromhex(hex(m)[2:]))

whitegive

hint

getPrime()生成的素数一般不会有大的公因子,$λ(N)$ 当成 $φ(N)$用问题不大

$$
λ(N) = \frac{p(p-1)(q-1)}{gcd(p-1,\ q-1)}
$$

$$
d^e e^e \equiv (de)^e \equiv (kλ(N)+1)^e \ (mod \ \ p^2q)
$$

$$
gcd(d^ee^e, p^2q) = p
$$

n = 1246903000089073759886267722667196003041462505274526737638837808213476294697746018085346623497511017543801377442390781101585650581984057653018703031659844145960721073451379508212905335383758157379301019575213158532070229897587088955814288202279949391608732448294591675986989254272257059551622461096394217684402667140362275595245430242117193793913872208576714597860532581116390903216389172132085635891741189355461016795362341416848534340615825023292174042406128959
e = 65537
hint = 788785744509676701442642497798353940704045062680685297430840370664093043099033424646382070232242765761123110381200239132310785932203252095093993313010883982078216697297202940152563278231011836966627537170460186597134847633828107444548759805274516431300662852153808962421740187067058018192457264083227110866080267684557127718769967184710395811547902947248700889674967381917907905535103547918375731341071557144999864774198881339085314424766509424492349867615604684

a1 = hint * pow(e, e) - 1

p = GCD(a1, n)
q = n // p // p

print(p*p*q)

c = 952508462840095293368043281511747192551431448088755251878915582522463097721381421883702408853564036431155676272901680250701398946525803160765527940151587567521509500006089852079864042238196362897144754722623523621230744820970423076092319608853809407595863195726851921082224085255808985329769890887863865121647796115540376158135632760785321953364738008064130705467326745546629505023549047992509562623348749056757848144371814157305011884825502144329268299851210747
print('e =', pow(c, inverse(e, (p**2 - p)*(q - 1)), n))
print(pow(c, inverse(e, (p**2 - p)*(q - 1)), n).bit_length())

小私钥boneh_durfee把d解出来

d = 103079922798932082066165266087442072203677117380612800709240732626110126828541
n = 97814568264814384858194701955408461509880555772006698372422205341758322175891474378211599333051180365254844248340812534463000531890490435018379585036704801177155418066770861143206836558793774360498040810255823235715535487716966004194143204900564413879660115112965484824906920141847149888933004740523449213441
c = 86143311788363675684674113699193046781796638913243016152555572150858159500527674063754694514501999791875561142925154991000532628799185608465062814546108160434468098898040769021072007374156546314975240583347468026001633652940408779155579339470960571067652924814623371177901052302005289155305089588204204313261
print(long_to_bytes(pow(c, d, n)))

Related Message Attacks

[Attack 4.4] Cryptanalysis of RSA and It's Variants

用SageMath实现RSA低指数攻击

也没太看懂,padding爆了一百多就出来了,多项式在环上求GCD,$sagemath$也不知道抽什么风,小的$Zmod(N)$可以,大一点就不行了,最后是求了 $groebner \ basis$ 算出来的m

N = 143224951702807798608353389056046982493788310072914995404719898237226283884553121669729599925829562704800197375580487019006702401282671268969358774635337351738915083955659230582177495821699251999928502338923489031347921151957398310960671307216790020399224115377846788378990638367296298663795893865325304226511
c1 = 74797173657575640598140788410852016843612519588375968190579734420951374103129570637822547217967978911328419808529204143522454142303138959013220811558490951614314306849367068478190797885056922705403028856734095288522290055309880572321557493798362056216783777593386133347693892941928131945986087712737862263761
c2 = 9209695919437085323423940852135308337887271742988391422139555924185234849146079306139570263602339983687993333013333937719071267190971983543492940032646907167417161479697805991443259327402389097539126399994414628326218438416138199892253597375493026563369334352434282120293396846427418323600336867792587721214

'''
PR.<x, b, c1, c2> = PolynomialRing(ZZ)
aa = x^7 - c1
bb = (x + b)^7 - c2
f = aa.resultant(bb)
print(f)
'''

PR.<b> = PolynomialRing(Zmod(N), 1)
f = b^49 + 7*b^42*c1 - 7*b^42*c2 + 21*b^35*c1^2 + 11963*b^35*c1*c2 + 21*b^35*c2^2 + 35*b^28*c1^3 - 187383*b^28*c1^2*c2 + 187383*b^28*c1*c2^2 - 35*b^28*c2^3 + 35*b^21*c1^4 + 424837*b^21*c1^3*c2 + 5150355*b^21*c1^2*c2^2 + 424837*b^21*c1*c2^3 + 35*b^21*c2^4 + 21*b^14*c1^5 - 187383*b^14*c1^4*c2 + 5150355*b^14*c1^3*c2^2 - 5150355*b^14*c1^2*c2^3 + 187383*b^14*c1*c2^4 - 21*b^14*c2^5 + 7*b^7*c1^6 + 11963*b^7*c1^5*c2 + 187383*b^7*c1^4*c2^2 + 424837*b^7*c1^3*c2^3 + 187383*b^7*c1^2*c2^4 + 11963*b^7*c1*c2^5 + 7*b^7*c2^6 + c1^7 - 7*c1^6*c2 + 21*c1^5*c2^2 - 35*c1^4*c2^3 + 35*c1^3*c2^4 - 21*c1^2*c2^5 + 7*c1*c2^6 - c2^7

for b in range(1, 2**20):
    if (f(b) % N) == 0:
        padding = b
        break

PR.<m> = PolynomialRing(Zmod(N), 1)
f1 = m^7 - c1
f2 = (m + padding)^7 - c2
I = Ideal(f1, f2)
gro_b = I.groebner_basis()[0]
m = -gro_b(0)
print(bytes.fromhex(hex(m)[2:]))
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇