sha & CTF记录

一个密码学菜狗

0%

螺丝网安工作室第二次例会：RSA

发表于 更新于 分类于
本文字数： 28k 阅读时长 ≈ 31 分钟

RSA介绍

数学基础

RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。

模运算与同余式

两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b mod m；例如：26 ≡ 14 mod 12。

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

欧拉函数

φ(n)的值表示小于等于n的正整数之中，有多少个数与n构成互质关系。

  1. 如果n=1，则 φ(1) = 1 。因为1与任何数都构成互质关系。
  2. 如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
  3. 如果n是质数的某次方，即 n = p^k (p为质数，k为大于等于1的整数)，则 \[ φ(p^k) = p^k-p^{k-1}=p^k*(1-\frac{1}{p}) \] 因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1) 个，即1×p、2×p、3×p、…、\(p^{(k-1)}×p\)，把它们去除，剩下的就是与n互质的数。
  4. 如果n可以分解成两个互质的整数之积，即n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)。

欧拉定理

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立： \[ a^{φ(n)}≡1 mod n \] 当n为质数时，欧拉定理可以化为： \[ a^{n-1}≡1 mod n \] 这就是费马小定理，它是欧拉定理的特例。

模反元素

当ab ≡ 1 mod n时，称b为a的模反元素，也称b为a在模n域下的逆。

RSA公私钥生成

  1. 加密者随机选择两个足够大的质数p和q（实际中通常选择512位）。
  2. 计算n = p*q。
  3. 计算φ(n) = (p-1)*(q-1)。
  4. 随机选择一个小于φ(n)且与φ(n)互质的e。
  5. 计算e在模n下的逆d，即e*d ≡ 1 mod φ(n)。
  6. (n, e)封装为公钥，(p, q, d)封装为私钥。

至此所有数据计算完成。

加密与解密

  1. 将密文转码为十六进制数据m。
  2. c ≡ m^e mod n，c 即为密文。
  3. m ≡ c^d mod n。

解密算法证明

\[ m^{φ(n)}≡1 modn\ m^{kφ(n)+1}≡m modn\ m^{ed}≡ c^d≡ m modn \]

各种题型介绍

已知n,e,c（直接分解）

n = 5221752478228507746817749923851271656160818214576859501288944132584319293315684653488045907979899837193635911723726962945029941498626499202969421505409311

c = 3508639296102512450759730723246544089341766434632407076573093985251751867216058996957915991315405129764052410967805084651073059790045344575535583118277973

e = 65537

在线分解大整数：http://www.factordb.com/

本地分解：yafu

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 5221752478228507746817749923851271656160818214576859501288944132584319293315684653488045907979899837193635911723726962945029941498626499202969421505409311
p = 72261694404632581565900073275105451175333931206466294424742649423557055375657
q = 72261694404632581565900073275105451175333931206466294424742649423557055375623
c = 3508639296102512450759730723246544089341766434632407076573093985251751867216058996957915991315405129764052410967805084651073059790045344575535583118277973
e = 65537
assert n == p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
print(long_to_bytes(pow(c, d, n)))

已知n,c,p,q(爆破e)

n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127 c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128 p = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183 q = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *

n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
p = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
q = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
phi = (p - 1) * (q - 1)

e = 2
for e in range(100000):
    if isPrime(e):
        try:
            d = invert(e, phi)
            flag = long_to_bytes(pow(c, d, n))
            flag = str(flag)
            if "CTF" in flag or "flag" in flag:
                print(e, '\n', flag)
                break
        except ZeroDivisionError:
            continue

已知n,e,c,dp(dp ≡ d mod(p-1))

e = 65537 n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847 c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869 dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

数学推导 \[ 已知dp ≡ d mod (p-1), e*d ≡ 1 mod(p-1)(q-1).\\可得edp ≡ ed mod(p-1).\\展开可得ed = edp +k_1(p-1) = 1 + k_2(p-1)(q-1).\\dp < p-1, e> k_2*(q-1)-k_1.\\ \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2
from Crypto.Util.number import *

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

for i in range(1, e):
    if (e * dp - 1) % i == 0 and n % ((e * dp - 1) // i + 1) == 0:
        q = n // ((e * dp - 1) // i + 1)
        phi = (q - 1) * ((e * dp - 1) // i)
        d = gmpy2.invert(e, phi)
        m = gmpy2.powmod(c, d, n)

print(long_to_bytes(m))

提取公钥/flag信息

1
2
3
4
5
6
7
8
9
10
11
from Crypto.PublicKey import RSA
path = r'C:\public.key'
with open(path) as f:
    key = RSA.import_key(f.read())
print('e = %d' % key.e)
print('n = %d' % key.n)
f = open('flag.enc', 'rb').read()
print(f)
e = 65537
tmp = int.from_bytes(f, byteorder='big')  # 高位存储
print(tmp)

在线工具：http://www.hiencode.com/pub_asys.html 解析公钥

共模攻击

n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801

c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361 e1 = 11187289 c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397 e2 = 9647291

数学基础：扩展欧几里得算法

$$ 扩展欧几里得算法可以在求出a,b的最大公约数的同时，求出满足ax+by = gcd(a, b)的x,y。

求最大公约数：欧几里得算法(辗转相除)

在到达辗转相除的递归边界时，b==0，a=gcd(a,b)。这时，a+b*0=gcd(a,b)，x=1,y=0

从递归的下一层往上一层推导，假设我们已知x_1,y_1使bx_1+(a mod b)y_1=gcd(b, (a mod b))=gcd(a,b)

首先已知a mod b = a - a // b * b

带回上一个式子： bx_1 + (a-(a//b)b)y_1= bx_1 + ay_1 – (a//b)by_1= a*y_1 + b(x_1 – (a//b)*y_1) = gcd(a,b)

x = y_1, y = x_1 - (a//b)*y_1 $$

解题推导

\[ 首先可知gcd(e_1, e_2) = 1，使用扩展欧几里得可以求出满足e_1*s_1+e_2*s_2 = 1的s_1和s_2。\ 又已知c_1 ≡ m^{e_1} mod n, c_2 ≡ m^{e_2} mod n,可得c_1^{s_1}*c_2^{s_2} mod n ≡ m^{(e_1*s_1+e_2*s_2)} ≡ m。 \]

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
from gmpy2 import invert
from Crypto.Util.number import *

def egcd(a, b):
    if b == 0:
        return a, 0
    else:
        x, y = egcd(b, a % b)
        return y, x - (a // b) * y


def gongmo(n, c1, c2, e1, e2):
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]
    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291
result = gongmo(n, c1, c2, e1, e2)
print(result)
print(long_to_bytes(result))

广播攻击

特点：给出多组n,c，使用同一个e加密。

解题思路1：遍历每对n,寻找是否有公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = [n0, n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, n15, n16, n17, n18, n19]
c = [c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19]

for i in range(len(n)):
    for j in range(len(n)):
        if i != j:
            if gmpy2.gcd(n[i], n[j]) != 1:
                print(i, j)  # 输出对应的n的序号
                p = gmpy2.gcd(n[i], n[j])
                print("p = ", p)
                q = n[i] // p
                print("q = ", q)
                d = gmpy2.invert(e, (p - 1) * (q - 1))
                print("d = ", d)
                m = pow(c[i], d, n[i])
                print("m = ", m)

解题思路2：中国剩余定理

数学基础

\[ 假设整数m_1,m_2,...m_n两两互素，则对于任意的整数a_1,a_2,...a_n，方程组\ \begin{equation} \begin{cases} x ≡ a_1 mod m_1 \ x ≡ a_2 mod m_2 \ ... \ x ≡ a_n mod m_n \end{cases} \end{equation} \]

\[ 都存在整数解，若X ,Y都满足该方程组，X ≡ Y modN，其中N=m_1*m_2*...*m_n。具体而言，\ x ≡ \sum_{i=1}^na_i\*\frac{N}{m_i}*[(\frac{N}{m_i})^{-1}]_{m_i}modN \]

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
36
37
38
from gmpy2 import *
from Crypto.Util.number import *
from functools import reduce

N1 = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c1 = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N2 = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c2 = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N3 = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c3 = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

N = []
c = []
for i in range(3):
    # 将题目给的所有值转成十进制并放进列表中
    N.append(int(str(eval('N' + str(i + 1))), 5))
    c.append(int(str(eval('c' + str(i + 1))), 5))
    print('N' + str(i + 1), '=', N[i])
    print('c' + str(i + 1), '=', c[i])


def chinese_remainder(modulus, remainders):
    Sum = 0
    prod = reduce(lambda a, b: a * b, modulus)
    for m_i, r_i in zip(modulus, remainders):
        p = prod // m_i
        Sum += r_i * (inverse(p, m_i) * p)
    return Sum % prod


e = 3
# print(chinese_remainder(N,c))
pow_m_e = chinese_remainder(N, c)
# pow_m_e = 17446992834638639179129969961058029457462398677361658450137832328330435503838651797276948890990069700515669656391607670623897280684064423087023742140145529356863469816868212911716782075239982647322703714504545802436551322108638975695013439206776300941300053940942685511792851350404139366581130688518772175108412341696958930756520037
m = iroot(pow_m_e, 3)[0]
print(long_to_bytes(m))

维纳攻击(低解密指数)

数学基础：连分数展开

\[ a = a_0+\frac{1}{a_1+\frac{1}{a2+\frac{1}{...}}} \]

简化为a=[a0;a1,a2,...an]记作对a的连分数展开。

连分数定理： \[ 当\mid x-\frac{a}{b} \mid<\frac{1}{2b^2}时，\frac{a}{b}是x的一个连分数近似。 \]

推导

\[ 当满足d<\frac{1}{3}N^{\frac{1}{4}}时，一定能分解N。\ 令λ(N)=lcm(p−1,q−1)=\frac{φ(N)}{g}，s = 1-p-q,\ 已知e*d = 1 + k*λ(N),则edg-kN=g+ks.\ 两边同除dgN得\frac{e}{N}-\frac{k}{dg}=(\frac{k}{dg})(\frac{s}{N})+\frac{1}{dN},\ 所以当d<\frac{\sqrt{2}}{2g}N^{\frac{1}{4}}时，\frac{k}{dg}是\frac{e}{N}的连分数近似。 \]

脚本：GitHub - pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme.

多项式RSA

Prime: 43753 Modulus: 34036y^177 + 23068y^176 + 13147y^175 + 36344y^174 + 10045y^173 + 41049y^172 + 17786y^171 + 16601y^170 + 7929y^169 + 37570y^168 + 990y^167 + 9622y^166 + 39273y^165 + 35284y^164 + 15632y^163 + 18850y^162 + 8800y^161 + 33148y^160 + 12147y^159 + 40487y^158 + 6407y^157 + 34111y^156 + 8446y^155 + 21908y^154 + 16812y^153 + 40624y^152 + 43506y^151 + 39116y^150 + 33011y^149 + 23914y^148 + 2210y^147 + 23196y^146 + 43359y^145 + 34455y^144 + 17684y^143 + 25262y^142 + 982y^141 + 24015y^140 + 27968y^139 + 37463y^138 + 10667y^137 + 39519y^136 + 31176y^135 + 27520y^134 + 32118y^133 + 8333y^132 + 38945y^131 + 34713y^130 + 1107y^129 + 43604y^128 + 4433y^127 + 18110y^126 + 17658y^125 + 32354y^124 + 3219y^123 + 40238y^122 + 10439y^121 + 3669y^120 + 8713y^119 + 21027y^118 + 29480y^117 + 5477y^116 + 24332y^115 + 43480y^114 + 33406y^113 + 43121y^112 + 1114y^111 + 17198y^110 + 22829y^109 + 24424y^108 + 16523y^107 + 20424y^106 + 36206y^105 + 41849y^104 + 3584y^103 + 26500y^102 + 31897y^101 + 34640y^100 + 27449y^99 + 30962y^98 + 41434y^97 + 22125y^96 + 24314y^95 + 3944y^94 + 18400y^93 + 38476y^92 + 28904y^91 + 27936y^90 + 41867y^89 + 25573y^88 + 25659y^87 + 33443y^86 + 18435y^85 + 5934y^84 + 38030y^83 + 17563y^82 + 24086y^81 + 36782y^80 + 20922y^79 + 38933y^78 + 23448y^77 + 10599y^76 + 7156y^75 + 29044y^74 + 23605y^73 + 7657y^72 + 28200y^71 + 2431y^70 + 3860y^69 + 23259y^68 + 14590y^67 + 33631y^66 + 15673y^65 + 36049y^64 + 29728y^63 + 22413y^62 + 18602y^61 + 18557y^60 + 23505y^59 + 17642y^58 + 12595y^57 + 17255y^56 + 15316y^55 + 8948y^54 + 38y^53 + 40329y^52 + 9823y^51 + 5798y^50 + 6379y^49 + 8662y^48 + 34640y^47 + 38321y^46 + 18760y^45 + 13135y^44 + 15926y^43 + 34952y^42 + 28940y^41 + 13558y^40 + 42579y^39 + 38015y^38 + 33788y^37 + 12381y^36 + 195y^35 + 13709y^34 + 31500y^33 + 32994y^32 + 30486y^31 + 40414y^30 + 2578y^29 + 30525y^28 + 43067y^27 + 6195y^26 + 36288y^25 + 23236y^24 + 21493y^23 + 15808y^22 + 34500y^21 + 6390y^20 + 42994y^19 + 42151y^18 + 19248y^17 + 19291y^16 + 8124y^15 + 40161y^14 + 24726y^13 + 31874y^12 + 30272y^11 + 30761y^10 + 2296y^9 + 11017y^8 + 16559y^7 + 28949y^6 + 40499y^5 + 22377y^4 + 33628y^3 + 30598y^2 + 4386y + 23814 Ciphertext: 5209x^176 + 10881x^175 + 31096x^174 + 23354x^173 + 28337x^172 + 15982x^171 + 13515x^170 + 21641x^169 + 10254x^168 + 34588x^167 + 27434x^166 + 29552x^165 + 7105x^164 + 22604x^163 + 41253x^162 + 42675x^161 + 21153x^160 + 32838x^159 + 34391x^158 + 832x^157 + 720x^156 + 22883x^155 + 19236x^154 + 33772x^153 + 5020x^152 + 17943x^151 + 26967x^150 + 30847x^149 + 10306x^148 + 33966x^147 + 43255x^146 + 20342x^145 + 4474x^144 + 3490x^143 + 38033x^142 + 11224x^141 + 30565x^140 + 31967x^139 + 32382x^138 + 9759x^137 + 1030x^136 + 32122x^135 + 42614x^134 + 14280x^133 + 16533x^132 + 32676x^131 + 43070x^130 + 36009x^129 + 28497x^128 + 2940x^127 + 9747x^126 + 22758x^125 + 16615x^124 + 14086x^123 + 13038x^122 + 39603x^121 + 36260x^120 + 32502x^119 + 17619x^118 + 17700x^117 + 15083x^116 + 11311x^115 + 36496x^114 + 1300x^113 + 13601x^112 + 43425x^111 + 10376x^110 + 11551x^109 + 13684x^108 + 14955x^107 + 6661x^106 + 12674x^105 + 21534x^104 + 32132x^103 + 34135x^102 + 43684x^101 + 837x^100 + 29311x^99 + 4849x^98 + 26632x^97 + 26662x^96 + 10159x^95 + 32657x^94 + 12149x^93 + 17858x^92 + 35805x^91 + 19391x^90 + 30884x^89 + 42039x^88 + 17292x^87 + 4694x^86 + 1497x^85 + 1744x^84 + 31071x^83 + 26246x^82 + 24402x^81 + 22068x^80 + 39263x^79 + 23703x^78 + 21484x^77 + 12241x^76 + 28821x^75 + 32886x^74 + 43075x^73 + 35741x^72 + 19936x^71 + 37219x^70 + 33411x^69 + 8301x^68 + 12949x^67 + 28611x^66 + 42654x^65 + 6910x^64 + 18523x^63 + 31144x^62 + 21398x^61 + 36298x^60 + 27158x^59 + 918x^58 + 38601x^57 + 4269x^56 + 5699x^55 + 36444x^54 + 34791x^53 + 37978x^52 + 32481x^51 + 8039x^50 + 11012x^49 + 11454x^48 + 30450x^47 + 1381x^46 + 32403x^45 + 8202x^44 + 8404x^43 + 37648x^42 + 43696x^41 + 34237x^40 + 36490x^39 + 41423x^38 + 35792x^37 + 36950x^36 + 31086x^35 + 38970x^34 + 12439x^33 + 7963x^32 + 16150x^31 + 11382x^30 + 3038x^29 + 20157x^28 + 23531x^27 + 32866x^26 + 5428x^25 + 21132x^24 + 13443x^23 + 28909x^22 + 42716x^21 + 6567x^20 + 24744x^19 + 8727x^18 + 14895x^17 + 28172x^16 + 30903x^15 + 26608x^14 + 27314x^13 + 42224x^12 + 42551x^11 + 37726x^10 + 11203x^9 + 36816x^8 + 5537x^7 + 20301x^6 + 17591x^5 + 41279x^4 + 7999x^3 + 33753x^2 + 34551*x + 9659

分解N为p和q后，p,q的欧拉函数为prime的p和q最高次方-1。

1
2
3
4
5
6
7
8
9
10
R.<y> = PolynomialRing(GF(43753))
N = 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
print(factor(N))
S.<x> = R.quotient(N)
e = 65537
phi = (43753^65-1)*(43753^112-1)# phi是不高于P(y)幂级的环内所有多项式中，与P(y)无公因式的其他多项式的个数
d = inverse_mod(e, phi)
c = 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659
print(c^d)
# 125*x^62 + 111*x^61 + 114*x^60 + 117*x^59 + 53*x^58 + 51*x^57 + 51*x^56 + 100*x^55 + 106*x^54 + 110*x^53 + 102*x^52 + 106*x^51 + 100*x^50 + 104*x^49 + 101*x^48 + 117*x^47 + 52*x^46 + 52*x^45 + 57*x^44 + 48*x^43 + 50*x^42 + 107*x^41 + 35*x^40 + 101*x^39 + 114*x^38 + 117*x^37 + 99*x^36 + 101*x^35 + 115*x^34 + 110*x^33 + 105*x^32 + 95*x^31 + 116*x^30 + 117*x^29 + 98*x^28 + 95*x^27 + 110*x^26 + 117*x^25 + 102*x^24 + 95*x^23 + 115*x^22 + 105*x^21 + 95*x^20 + 97*x^19 + 101*x^18 + 107*x^17 + 105*x^16 + 95*x^15 + 109*x^14 + 111*x^13 + 114*x^12 + 102*x^11 + 95*x^10 + 65*x^9 + 83*x^8 + 82*x^7 + 123*x^6 + 114*x^5 + 118*x^4 + 101*x^3 + 116*x^2 + 97*x + 119

coppersmith攻击:已知p高位

数学基础：格基规约

格基规约算法：数学基础_随缘懂点密码学的博客-CSDN博客_格基约化算法

格基规约算法：算法详解_随缘懂点密码学的博客-CSDN博客_格基规约

[LLL算法在RSA安全分析中的应用][LLL算法在RSA安全性分析中的应用_知网百科 (cnki.net)](https://security.feishu.cn/link/safety?target=https://xuewen.cnki.net/ArticleCatalog.aspx?filename=1013353564.nh&dbtype=CMFD&dbname=CMFD201401&scene=ccm&logParams={"location":"ccm_drive"}&lang=zh-CN)

p为1024位时，需最高知道p的高位的576位，位数不够时需爆破。 \[ 在这个问题中，我们的目标是找到模N意义下多项式f所有的根，通过LLL算法，我们能找到\ 与该多项式具有相同的根x_0,\ 更小系数，\ 定义在整数域，\ 上的多项式g。从而我们就得到了原多项式在模意义下的整数根. \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from sage.all import *
n = 25348605574630284342864323710011622959543974652863854537355760576386763162531478272446867731299572532294812374775121121761898206639041068156270466457595336452690367719842145233764550634280981441631262047763246059814963741143303914063537003244814908763379320576260885158458898112416692583017869283284022878603506583499699525249773663841642694427307104140944360804367072787670581252816486834658346431010523135392357008103555699542414687172408709153334263858639251735462278292703380745537045458408951791720967957274781161667526873251066303708008043058246747534357368350540174588670636827470901518225473676343782182718627
p4 =0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000 
e = 0x10001
pbits = 1024
for i in range(0,4096):
    p4=0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000
    p4=p4+int(hex(i),16)
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2^kbits, beta=0.4)
    if roots:
        p = p4+int(roots[0])
        print( "n: ", n)
        print("p: ", p)
        print ("q: ", n//p)
        break