RSA

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特(Ron Rivest)、阿迪 · 萨莫尔(Adi Shamir)和伦纳德 · 阿德曼(Leonard Adleman)一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的

密钥生成

  1. 选两大素数 p, q

  2. 计算模数:

\[ N = p \cdot q \]
  1. 计算欧拉函数:
\[ \varphi(N) = (p-1)(q-1) \]
  1. 选一个公开指数 e,满足:
\[ \gcd(e, \varphi(N)) = 1 \]
  1. 计算私钥指数:
\[ d \equiv e^{-1} \pmod{\varphi(N)} \]
  • 公钥:(N, e)
  • 私钥:(N, d)

加密

给定明文整数 m(要求 0≤m<N):

\[ c \equiv m^e \pmod{N} \]

就是把 m 用 e 次幂提升,再对 N 取模。在 Python 里对应:

1
c = pow(m, e, N)

解密

拿到密文c:

\[ m \equiv c^d \pmod{N} \]

Python:

1
m = pow(c, d, N)

1.公钥解析

对于.pem和.key结尾的文件,可以用工具解析出n和e,也可以使用Openssl从公钥文件中提取出n和e

SSL在线工具-公钥解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from cryptography.hazmat.primitives import serialization

pem_data = b"""
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
-----END PUBLIC KEY-----

"""

# 加载公钥
public_key = serialization.load_pem_public_key(pem_data)

# 获取 public numbers
numbers = public_key.public_numbers()

n = numbers.n
e = numbers.e

print("Modulus (n) =", n)
print("Exponent (e) =", e)

2.小明文攻击

一般e很小

1
2
3
4
5
6
7
p = getPrime(5120)
q = getPrime(5120)

n = 1392208858696945158251408085300402884210409327605255122395601049457847957306648819174395014931778575812308192875319127224095733396726388842605854427013313599830150182564652493067830031524869535522568868597852507293377043240832819715539722122306829543983051745406887140154364256267942350230636870212935356815475345989038318923389132101208917912083817520799490534351545373438629367819085151041702754019127891155542476560972125790519584018715794669416759039955180436830478697704458250990786586357019211642837879273967620287257818400267757312623543898635740200839249361087580046496969637043238450499583879116276661827372750638403042213043389905183760455450595752578482968202040860053524276678108325784161897719093223308370971388068813420487879756084379519128232693549989942550047529174783976176943482484756074638704076740157397067892580297182979526978967352014250386678155843772313996171396582929433057131989693861316408604436872931427368192437680361830753162284661119995125858203931094922686321756465463988790748131178263745308042820480140189644732824717255521633534750635979508673908361269979175726073254050574688259969290376926807033728165164896588540691889207252105903436659968119091774687841336252628343233161941187968365128093917171537997137001140227677728923114895809278926486615010954871408034272872411042537353956193868948909981683850857262457369506288525323882308421700421661036191853577105238753230479541719001794464585534292774768292358961920606891227776349593589481547577148801600196035588544512224775960892265021565124673788852875005526313525709353599584812394138968970647681759439523307392275602626903789154682706839530654070108096741181206975334567778238856983205004289416400671597321919876279909765650782227834097342294844294386380646928266942749144240020420237153276705785759403019072953506982997681174635673907151856644499332322321579088035719680421458310273802481031746012298208449699089203065699598926690947025679591160106357130634946357609420125223580319677387654711233585375013067828291928349946599077331636017784447090096340360087970540477975170379810969501197027775838769222713506443846417124839450184827707739588007707714623211453528342755023849716924694572679150284882978804641986457119009272574734697043321033091757474387114449914271460113979531460465175717705674905568446670579332667139075523255580471183372714211547822093365025438653384719374474230360983878837077517864405475258349436531094649276628214288499716485354283135575921258757214288792410583835467572916298688718758374714560819702413058421373661892101033513816116981698045524150518509405086125781764762145577981637953775680403132163846782252745029783387112660812179706752454175492501665442704630131729362621965258498471247871904163412798544329515689112368523703890083138721480476796720323855371775568097188216621368341228806795058046403892301673157631331636430392885315997250027372621883549649614866115616619234953579196607399899485002042456482969222428121605212017146571466818179341621066715472184636758016242256725063854155219754299817717414423725704356940589670902509021070871847017199593680033
e = 97
phi = (p-1)*(q-1)
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125

由

\[ c \equiv m^e \pmod{N} \]
\[ 当m^e很小时,对N取模后并不会丢失信息,相当于c =m^e \]
1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

def small_msg_rsa(N, e, c):
m, exact = iroot(c, e)
return long_to_bytes(int(m)) if exact and pow(int(m), e) < N else None

N =
e =
c =
print(small_msg_rsa(N, e, c))

3.低加密指数攻击

一般e=3

1
2
3
4
5
n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e: 0x3
c: 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
#so,how to get the message?

\[ 当 𝑚^𝑒&lt;𝑛时,即为小明文攻击 \]
\[ 当 𝑚^𝑒&gt;𝑛时,𝑚𝑒=𝑘𝑛+𝑐,对k进行爆破 \]

此题满足

\[ m^3&lt;n \]

可以使用第一个脚本攻击,这里给出对k爆破的脚本,也能求解

\[ 因为已知𝑚^3&lt;n,m^3=kn+c,那么必然k=0,即flag=0⋅n+c=c=m^3 \]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from gmpy2 import *
from Crypto.Util.number import *
import math
n =
e =
c =

k = 0
while True:
# 计算一个候选值
flag = k * n + c
# 检查这个候选值是否是一个完美的e次方
if iroot(flag, e)[1]:
# 如果是,就计算它的e次方根
m = iroot(flag, e)[0]
print(long_to_bytes(m))
break
k += 1


4.共模攻击

特征:

  • 同一个模数 N

  • 同一个明文 m

  • 两个不同指数 e1, e2(互质)

\[ 已知𝑐1=𝑚^{e1} mod𝑁,𝑐2=𝑚^{e2} mod𝑁 \]

攻击思路:

  1. 求 egcd(e1,e2)=1的扩展欧几里得系数:
\[ a e_1 + b e_2 = 1 \]
  1. 根据:
\[ m = m^{a e_1 + b e_2} = m^{a e_1} \cdot m^{b e_2} \equiv c_1^a \cdot c_2^b \pmod{N} \]
  1. 得到 m,再 long_to_bytes(m) 还原明文
1
2
3
4
5
6
7
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}

{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}

message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599

message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
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
import gmpy2
from libnum import n2s, s2n

# 扩展欧几里得算法:求a和b的gcd及贝祖系数
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

# RSA共模攻击参数(合并多行大整数,去除换行)
e1 = 2767
e2 = 3659
n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

# 计算贝祖系数
g, s1, s2 = egcd(e1, e2)
print(f"gcd(e1, e2) = {g}, s1 = {s1}, s2 = {s2}")

# 处理负系数:若系数为负,对对应密文求模逆
if s1 < 0:
s1 = -s1
c1 = gmpy2.invert(c1, n) # 求c1在模n下的逆元
if s2 < 0:
s2 = -s2
c2 = gmpy2.invert(c2, n) # 求c2在模n下的逆元

# 计算明文m = (c1^s1 * c2^s2) mod n
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n

# 将整数明文转换为字符串
plaintext = n2s(int(m))
print("解密后的明文:", plaintext.decode('utf-8')) # 解码为UTF-8字符串

5.共享素数

特征:

  • 有两个(或多个)RSA 公钥:
\[ N_1 = p \cdot q_2,\quad e_1 \]
\[ N_2 = p \cdot q_2,\quad e_2 \]
  • 共用了同一个素数 p,但另一个因子 q1, q2 不同

  • 攻击者拿到N1, e1和 N2, e2,不知道 p,q1,q2

攻击思路:

N1=pq1,N2=pq2

那么他们的最大公因数p=gcd(N1,N2)

\[ 那么q1=\frac{N1}{p},q2=\frac{N2}{p} \]

剩下正常RSA解密即可

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
from Crypto.Util.number import getPrime
from binascii import hexlify
from hashlib import md5
from random import choices
from string import hexdigits
import gmpy2
from flag import flag

nbits = 1024
flaga = int(hexlify(flag[0:16].encode()), 16)
flagb = int(hexlify(flag[16:].encode()), 16)
e = 65537

prime_1 = getPrime(nbits)
prime_2 = getPrime(nbits)
prime_3 = getPrime(nbits)

n1 = prime_1 * prime_2
n2 = prime_2 * prime_3

assert flaga < n1 and flagb < n2

enc1 = pow(flaga, e, n1)
enc2 = pow(flagb, e, n2)

print('[+] n1 =', n1)
print('[+] n2 =', n2)

print('[+] enc1 =', enc1)
print('[+] enc2 =', enc2)

[+] n1 = 11765097365866108944467221067206463780779980110268391493819443451219718091560660309180700246601735229671361868645564516245649407502928848069352545156278660222578544379497469105940730101468595186834660076063646016840687675531091875958082161034626079806535227527564029567123620928137861037306182166286845556302199398031604369084893258864871870767644694738889568791598969434421695136039301294435150544548371273941643917600723425709165333782025111145656982953598604346014961180575302009875197979217304489174093283721922156389840034181036025893694664462891089421965035128367837944061456049481435173068825298797858500820369
[+] n2 = 12234531436509958361276371161256481332359794279664677748577726048643264743971136918597315461863966323614404483302397649026177922843601519154949663608529889374554245303997962575204931930656878417050660224278237635240897068811529609301434664205971687828868106894394932260872607641138168595559040055256155252649692790618084795082657366815523434795597614280221260674597647533192168141259797675613588275315104567017642710611852576367526835606875181733404489113428803804888140961099552216877174726907294852706696495569170863685126412036755571517520020575629874454530043875627718377356252485788446200229508550230459230268793
[+] enc1 = 499331446739848021575488055959844542435059327263628125975337905355387242902837757588646730593373932964932239418218163602018988171343848829971780775811749067259148633677054264293673117838115112032556274460491321464784105849075714617535248954663670763988300576700194765373605619855573875419600620299342354583558574294831395221012758866869326541292815658042721530763515869474508621774583825230425235906834308420199551390661437604589646123161462314591200470888968839541276867493503636243086320355234869050014182663343576295908547428247521489038524685926787469834717128493894052671107947921150046758014852122862063560195
[+] enc2 = 1318141536502632613045128291461111926174588932299377884303729367417850534880395642656862320885171220246769063129491614535443531694706076611948855191239193068286693242728534093746330463305299177322539033474275543804396380101912881062454065948457465680906263960344781093187376446372387916988678832092970303465128258206123774633266457576681663014712994198124315213715497791209940266596908833368579968026791178550261902658959310223990682439571329144943650980277696117943239198625350827688129955312420276272214056037166913291160755202318693778058611747212303140613427703240914323529146581927812387097472836228133843994320

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
from math import gcd
from Crypto.Util.number import long_to_bytes

def shared_prime_attack(n1, n2, e1, e2, c1, c2):
p = gcd(n1, n2)
assert p != 1
q1, q2 = n1 // p, n2 // p

phi1 = (p - 1) * (q1 - 1)
phi2 = (p - 1) * (q2 - 1)

d1 = pow(e1, -1, phi1)
d2 = pow(e2, -1, phi2)

m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)

return long_to_bytes(m1), long_to_bytes(m2)

n1 =
n2 =
e1 = e2 = 65537
c1 =
c2 =

m1, m2 = shared_prime_attack(n1, n2, e1, e2, c1, c2)
print(m1, m2)

6.费马分解(p-q过小)

适用于p-q过小

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
39
40
41
42
43
44
import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()


#N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
#m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
#m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

关注方法sympy.nextprime(n),它会返回严格大于n的最小素数

这题就是

  1. 先造一个很大的数 secret_num(1024bit prime × secret)
  2. p = nextprime(secret_num):取大于 secret_num 的第一个质数
  3. q = nextprime(p):再取大于 p 的下一个质数
  4. 所以 p 和 q 是相邻质数,差值很小

拿代码举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2

n=118816369182219711551736875622148948376274930097622029542291351942110204065005093752267272235864774888160522170555189015695148555668006209122716634896476014952586332120668094812890443697140874554631953248467119041951362983074748376348829077644413780641030688747863975973112631445365138922148115802917498155841

temp = gmpy2.iroot(n, 2)[0]
p = gmpy2.next_prime(temp)
q = n // p
print(p)
print(q)

"""
就是现在p,q是两个素数,而且他俩在素数序列里面就是一前一后的关系。所以我们要把他俩的乘积开根号得到的结果一定是在p,q之间的一个数字,(而且一定不是素数,因为p,q就是紧邻的两个素数)。

那我们找这个开方出来的数字的下一个素数,一定是q,因此我们再让n/q就可以得到两个素数。(必须得保证两个数为素数,而且挨得很近才行)
"""

得到了p,q,剩下解方程就行

7.Rabin

密钥生成:

  1. 选两个大素数 p, q,通常要求:
\[ p \equiv q \equiv 3 \pmod 4 \]

这是为了让解密过程(平方根)更简单、形式唯一

  1. 计算:
\[ N = p q \]
  1. 公钥:N
    私钥:p, q

加密过程:

给定明文整数 m(满足0 ≤ m<N):

\[ c \equiv m^2 \pmod N \]

解密过程:

\[ 已知c=m^2 mod N,以及私钥p,q,求出m \]
  1. 分别在模 p 和模 q 上求平方根 :
\[ m_p^2 \equiv c \pmod p \]
\[ m_q^2 \equiv c \pmod q \]

由于 p 和 3对4同余 , 可以用一个简单公式求平方根:

\[ m_p \equiv c^{\frac{p+1}{4}} \pmod p \]

同样:

\[ m_q \equiv c^{\frac{q+1}{4}} \pmod q \]
\[ 每个模下其实有两个根:\pm m_p \pmod p、\pm m_q \pmod q \]
  1. 再用中国剩余定理把 四个根组合成 4 个模 N 的解:

    • 解方程组:
\[ x \equiv \pm m_p \pmod p \]
\[ x \equiv \pm m_q \pmod q \]

所以,对于给定密文 c,一般会有 4 个平方根,即对应 4 个可能的 m。

1
2
3
n = 201354090531918389422241515534761536573
c = 20442989381348880630046435751193745753
e = 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
import libnum

p =
q =
n =
c =
e =

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
aa = [a, b, c, d]

for i in aa:
print(i)

print(libnum.n2s(int(i)))

8.dp泄露

1.e较小

已知N, e, dp, c

\[ dp=dmod(p-1) \]

把RSA的加密步骤拆开来看

RSA 私钥 d 满足:

\[ e d \equiv 1 \pmod{\varphi(N)} \]

对于素数 p、q,有:

\[ \varphi(N) = (p-1)(q-1) \]

所以必然也有:

\[ ed \equiv 1 \pmod{p-1} \]

根据Dp的定义,意味着一定存在整数Kp,使得下式成立:

\[ d =dp+kp(p-1) \]

将此式代入得

\[ e d_p - 1 = k_p (p-1) \]

这里 Kp, Kq是某些正整数,最后化简得

\[ p=\frac{ed_p-1}{K_p}+1 \]

接下来便是对k的枚举

1
2
3
4
n =156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
dp =734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
c =108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
e =65537
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
from Crypto.Util.number import *
n =
dp=
c =
e =
tmp = e * dp -1
#根据联立条件有: e*dp = 1 + k(p-1),故求解p的式子为:(p-1) = (e*dp-1) / k
for k in range(1, e):#因为K上限只到e,故遍历求解
if tmp % k == 0:#验证(p-1)是否为整除结果
p = (tmp // k) + 1
if n % p == 0:#验证p能否被n整除
q = n // p
if gmpy2.is_prime(p) and gmpy2.is_prime(q):#验证求解的p, q是否为素数
# print(k)
print("N的分解结果为 : ")
print("%d = %d * %d" % (n, p, q))
break
phi = (p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

2.e较大

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

flag = b'NSSCTF{******}' + b'1'*80

p = getPrime(512)
q = getPrime(512)

n = p*q
e = getPrime(128)
d = inverse(e, (p-1)*(q-1))

dp = d % (p-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f'dp = {dp}')

'''
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
'''

当e比较大时,我们构造p的倍数,再用gcd分解n

无论 e 多大,只要知道 dp,就有:

\[ e⋅dp \equiv 1 \mod(p-1)⇒e⋅dp=1+k(p−1) \]

对任意整数 a mod p != 0,由 Fermat 小定理:

\[ a ^{p−1} ≡1(modp)⇒a^ {e⋅dp} =a ^{ 1+k(p−1)} ≡a⋅(a^{ p−1} ) ^ k ≡a(modp) \]

所以:

\[ a ^{e⋅dp} −a≡0(modp)⇒p∣(a^{ e⋅dp} −a) \]

但通常 q 不能整除 (a^(e * dp) - a),因此:

\[ p=gcd(a ^{ e⋅dp} −a, n) \]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import math


n =
e =
c =
dp =


for a in range(2, 10):
# 关键一步:计算 a^(e * dp) mod n
x = pow(a, e * dp, n)
p = math.gcd(x - a, n)
if 1 < p < n:
print(f"[+] p = {p}")
q = n // p
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
break

9.pollard‘s p-1

前置概念:

1.光滑数(Smooth Number)

光滑数(smooth number),或译脆数:是一个可以约数分解为小素数乘积的正整数。光滑数一词是是伦纳德·阿德曼所提出,光滑数在以约数分解为基础的密码学中扮演重要角色

若一个数的所有质因子都 ≤ B,就叫 B-光滑(B-smooth)

2.费马小定理(Fermat’s little theorem)

如果p是一个质数,而整数a不是p的倍数,则有

\[ a^{p-1}≡1mod p \]

攻击思路:

当已知p-1为光滑数时,题目代码通常包含

1
2
3
4
5
6
7
def myPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1

这里采用提问的方式应该更能弄清原理

问题 1️⃣:

我现在知道了 p-1 的素因子都很小,那我试着“制造一个跟 p-1 有关的东西”,这个“东西”应该满足什么性质,才能帮我把 p 从 N 里抠出来?

我们可以构造一个数S,使得:

S 被 p 整除(p | S), S 不被 q 整除

即

\[ gcd(S,N)=p \]

问题 2️⃣:

那么我们该怎么构造被p整除的数?

费马小定理:

\[ \text{如果 }p\text{ 是素数,且 } \gcd(a,p)=1,\text{ 那么 }a^{p-1} \equiv 1 \pmod p \]

推一下:

\[ a^{p-1} \equiv 1 \pmod p \Rightarrow a^{p-1} - 1 \equiv 0 \pmod p \Rightarrow p \mid (a^{p-1} - 1) \]

所以:

如果我能算出 a^(p-1) - 1,那么它一定能被 p 整除

那我们的“候选 S”自然就可以选:

\[ S = a^M - 1 \]

只要 M 是 p-1 的倍数,比如 M = k (p-1),那一样有:

\[ a^M = a^{k(p-1)} \equiv 1^k \equiv 1 \pmod p \Rightarrow p \mid (a^M - 1) \]

问题 3️⃣:

M 是 (p−1) 的倍数,但 p−1 是未知的那我凭什么构造出这样的 M?

假设我们知道:

p-1 的所有质因子都 ≤ B。
比如 B=5,就是说 p−1 只可能由 2,3,5 这些质数相乘组成。

举一个例子

  • 假设:
\[ p-1 = 2^3 \cdot 3^2 \cdot 5^1 = 8 \cdot 9 \cdot 5 = 360 \]
  • 它的质因子就是 2,3,5,都 ≤ 5

那我们怎么“盲选”一个 M,让它一定能被所有这些小质因子的幂整除?

我们可以把所有“小质数的若干次方”都塞进 M 里

我们可以这样构造 M:

  • 找到每个质数的“最大幂次”,让它不超过某个界 B
    举例:B=16

    • 对 2:最大幂是 2^4 = 16
    • 对 3:最大幂是 3^2 = 9
    • 对 5:最大幂是 5^1 = 5
  • 用它们乘起来:

\[ M = 2^4 \cdot 3^2 \cdot 5^1 = 16 \cdot 9 \cdot 5 = 720 \]

这时看看我们真实的 p-1=360:

\[ 360 = 2^3 \cdot 3^2 \cdot 5^1 \]

对比一下:

  • 在 M 里:
    • 2 的幂是 4(≥3)
    • 3 的幂是 2(=2)
    • 5 的幂是 1(=1)

所以 360 一定整除 720,即:

\[ p-1 = 360 \mid M = 720 \]

结论:只要我构造的 M 把所有小质数的幂都“堆够高”,p−1 一定整除 M。

问题 4️⃣:

有了 M 之后,接下来对什么取 gcd,能得到 p?

因为

\[ a^M \equiv 1 \pmod p \Rightarrow p \mid (a^M - 1) \]

对于 q,一般不会有 q-1整除M,所以通常 q 不会整除 a^M-1。

于是:

  • p | (a^M−1)
  • p | N
  • 但 q 一般不 | (a^M−1)

因此:

\[ \gcd(a^M - 1, N) = p \]

具体可以参考:

大整数分解算法 之 Pollard’s p-1 算法原理 - TLSN - 博客园

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 long_to_bytes
import gmpy2
N =
c =
e=
a = 2
n = 2
while True:
a = pow(a, n, N)
res = gmpy2.gcd(a-1, N)
if res != 1 and res != N:
q = N // res
print("n=",n)
print("p=",res)
print("q=",q)
break
n += 1
d=gmpy2.invert(e,(res-1)*(q-1))
m=pow(c,d,N)
print(long_to_bytes(m))

10.William’s p+1

如果要分解的数N包含一个或多个素数因子p,且p+1是光滑的(即p+1只包含小的因子),那么Williams’s p+1有效。Williams’s p+1使用Lucas序列在二次域中执行求幂运算,它类似于Pollard的p−1算法。

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
39
40
41
42
43
44
45
46
47
48
49
50
from math import isqrt
from gmpy2 import gcd
from Cryptodome.Util.number import long_to_bytes
from itertools import count
from sympy import primerange

# 示例已知参数,待分解的n
n =
# Lucas 序列(Williams p+1 用的)
def mlucas(v, a, n):
v1, v2 = v, (v ** 2 - 2) % n
for bit in bin(a)[3:]:
if bit == "0":
v1, v2 = (v1 ** 2 - 2) % n, (v1 * v2 - v) % n
else:
v1, v2 = (v1 * v2 - v) % n, (v2 ** 2 - 2) % n
return v1

# 素数生成器
def primegen():
yield from primerange(2, 10**6) # 生成到 10^6 的素数,够用了

# 整数对数:ilog(x, b) = 最大整数 l,使得 b^l <= x
def ilog(x, b):
l = 0
while x >= b:
x //= b
l += 1
return l

# Williams p+1 分解攻击
def attack(n):
for v in count(1): # 不断尝试新的 v
for p in primegen():
e = ilog(isqrt(n), p)
if e == 0:
break
for _ in range(e):
v = mlucas(v, p, n)
g = gcd(v - 2, n)
if 1 < g < n:
return int(g), int(n // g)
if g == n:
break

# 开始攻击
p1, q1 = attack(n)
print(f"p = {p1}")
print(f"q = {q1}")

11.Wiener

当私钥d足够小时,公钥e和模数n的比值可以通过连分数逼近的方法找到私钥d。再具体点来说,就是通过连分数逼近的方法,对 e/n进行连分数展开来逐步逼近真实的私钥。通过这种方法,攻击者能够恢复出满足RSA方程的有效私钥d

攻击条件 :

\[ d&lt; \frac{n^{\frac{1}{4}}}{3} \]

攻击原理 :

\[ ed \equiv 1 \pmod{\varphi(n)} \]

等价于存在整数 k,使得:

\[ ed - k\varphi(n) = 1 \]

即:

\[ ed = k\varphi(n) + 1 \]

这里 k 和 d 同阶,且都较小(这是攻击能成立的前提之一)

两边同时除以 d*phi(n):

\[ \frac{e}{\varphi(n)} = \frac{k}{d} + \frac{1}{d\varphi(n)} \]

又因为 :

\[ \varphi(n) = (p-1)(q-1) = n - (p+q) + 1 \]

当 p,q同数量级时:

\[ \varphi(n) \approx n \]

于是:

\[ \frac{e}{n} \approx \frac{e}{\varphi(n)} \]

从而:

\[ \frac{e}{n} \approx \frac{k}{d} \]

Wiener 证明的关键是:

\[ \left| \frac{e}{n} - \frac{k}{d} \right| &lt; \frac{1}{2d^2} \]

而连分数定理告诉我们:

若

\[ &gt; \left| x - \frac{a}{b} \right| &lt; \frac{1}{2b^2} &gt; \]

则 \frac{a}{b} 必是 x 的某个连分数收敛项

因此:

\[ \frac{k}{d} \text{ 一定出现在 } \frac{e}{n} \text{ 的连分数收敛项中} \]

那我们需要做的就是对连分数展开 :

\[ \frac{e}{n} = [a_0; a_1, a_2, \dots] \]

并生成所有 convergent(收敛项):

\[ \frac{k_0}{d_0}, \frac{k_1}{d_1}, \frac{k_2}{d_2}, \dots \]

接下来便是对每个收敛项进行枚举, 满足下述条件 :

\[ ed_i - 1 = k_i \varphi(n) \]

若 不能整除,则直接跳过:

1
2
if (e*d - 1) % k != 0:
continue
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import gmpy2
from math import isqrt

def continued_fraction(n, d):
"""生成连分数"""
cf = []
while d:
q = n // d
cf.append(q)
n, d = d, n - q * d
return cf

def convergents(cf):
"""由连分数生成收敛项 k/d"""
convs = []
for i in range(len(cf)):
num, den = 1, 0
for q in reversed(cf[:i+1]):
num, den = den + num * q, num
convs.append((num, den))
return convs

def wiener_attack(e, n):
cf = continued_fraction(e, n)
for k, d in convergents(cf):
if k == 0:
continue

# ed ≡ 1 (mod φ(n))
if (e * d - 1) % k != 0:
continue

phi = (e * d - 1) // k
s = n - phi + 1 # p + q
delta = s * s - 4 * n

if delta < 0:
continue

t = isqrt(delta)
if t * t == delta:
p = (s + t) // 2
q = (s - t) // 2
if p * q == n:
return d, p, q

return None

if __name__ == "__main__":
e =
n =

res = wiener_attack(e, n)
if res:
d, p, q = res
print("[+] Wiener Attack Success!")
print("d =", d)
print("p =", p)
print("q =", q)
else:
print("[-] Attack Failed")

Wiener攻击已被更强大的RSA加密方法取代,如Franklin-Reiter相关消息攻击和Boneh-Durfee攻击,后者即使私钥指数相对于模数不小,也能恢复私钥

12.Boneh-Durfee

和wiener攻击很像,在给定了N和e的情况下,发现d很小

攻击条件:

\[ d&lt;N^{0.292} \]

攻击原理:

回到已知公式 :

\[ ed \equiv 1 \pmod{\varphi(N)} \]

变形 :

\[ ed - k\varphi(N) = 1 \]

化简 φ(N) :

\[ \varphi(N) = N - (p+q) + 1 \]

代入:

\[ ed - kN + k(p+q-1) = 1 \]

这里:

\[ p≈q≈N ​ \]

所以:

\[ p+q \approx 2\sqrt{N} \]

准确一点:

\[ p+q = 2\sqrt{N} + \varepsilon,其中|\varepsilon| \ll \sqrt{N} \]

引入一个”已知常数”A,满足 :

\[ A \approx p+q-1 \]

注意:A 是你选的,不是等于 p+q−1

写成:

\[ p+q-1 = A + \Delta \]

其中:

\[ \Delta = (p+q-1) - A \]

代入原式 :

\[ k(p+q-1) = k(A+\Delta) \]

代入 :

\[ ed - kN + kA + k\Delta = 1 \]

整理:

\[ ed - kN + kA - 1 = -k\Delta \]

假设 kΔ=非常小,于是 :

\[ ed - kN + kA - 1 \approx 0 \]

**引入多项式 **:

令:

\[ x = d,\quad y = k \]

定义多项式:

\[ \boxed{ f(x,y)=ex-yN+yA-1 } \]

于是:

\[ f(d,k) \approx 0 \]

更重要的是:

\[ f(d,k) \equiv 0 \pmod{N} \]

后面再引入CooperSmith方法 :

若存在多项式

\[ &gt; f(x,y) \equiv 0 \pmod N &gt; \]

且其整数根满足:

\[ &gt; |x| &lt; X,\ |y| &lt; Y &gt; \]

并且 X,Y 足够小,
则可以通过构造格并应用 LLL 算法恢复该根。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
from __future__ import print_function
import time

############################################
# Config
##########################################

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1

print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB

# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj

# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB

# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
print("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# nothing happened
return BB

"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May

finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""

# substitution (Herrman and May)
PR.<u, x, y> = PolynomialRing(ZZ)
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()

UU = XX*YY + 1

# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()

# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()

# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution

# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)

# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print("failure")
return 0,0

# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus^mm)

# check if determinant is correctly bounded
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print("We do not have det < bound. Solutions might not be found.")
print("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

# display the lattice basis
if debug:
matrix_overview(BB, modulus^mm)

# LLL
if debug:
print("optimizing basis of the lattice via LLL, this can take a long time")

BB = BB.LLL()

if debug:
print("LLL is done!")

# transform vector i & j -> polynomials 1 & 2
if debug:
print("looking for independent vectors in the lattice")
found_polynomials = False

for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

# resultant
PR.<q> = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)

# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break

if not found_polynomials:
print("no independant vectors could be found. This should very rarely happen...")
return 0, 0

rr = rr(q, q)

# solutions
soly = rr.roots()

if len(soly) == 0:
print("Your prediction (delta) is too small")
return 0, 0

soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]

#
return solx, soly

def example():
############################################
# How To Use This Script
##########################################

#
# The problem to solve (edit the following values)
#

# the modulus
N =
# the public exponent
e =

# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = .18 # this means that d < N^delta

#
# Lattice (tweak those values)
#

# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 # size of the lattice (bigger the better/slower)

# you need to be a lattice master to tweak these
t = int((1-2*delta) * m) # optimization from Herrmann and May
X = 2*floor(N^delta) # this _might_ be too much
Y = floor(N^(1/2)) # correct if p, q are ~ same size

#
# Don't touch anything below
#

# Problem put in equation
P.<x,y> = PolynomialRing(ZZ)
A = int((N+1)/2)
pol = 1 + x * (A + y)

#
# Find the solutions!
#

# Checking bounds
if debug:
print("=== checking values ===")
print("* delta:", delta)
print("* delta < 0.292", delta < 0.292)
print("* size of e:", int(log(e)/log(2)))
print("* size of N:", int(log(N)/log(2)))
print("* m:", m, ", t:", t)

# boneh_durfee
if debug:
print("=== running algorithm ===")
start_time = time.time()

solx, soly = boneh_durfee(pol, e, m, t, X, Y)

# found a solution?
if solx > 0:
print("=== solution found ===")
if False:
print("x:", solx)
print("y:", soly)

d = int(pol(solx, soly) / e)
print("private key found:", d)
else:
print("=== no solution was found ===")

if debug:
print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
example()

其中上述代码的deltaz可以修改

其中参数 δ 表示对私钥 d 的规模假设,
即假设 d < N^delta。
根据 Boneh–Durfee 理论,当
delta < 1 - √2/2
时可通过格方法恢复私钥。
在实际攻击中,δ 需从较小值开始逐步增大,
以平衡格维度与 LLL 的可行性。

13.Franklin-Reiter

如果两条消息的区别仅在于两条消息之间的已知固定差异 , 并且是在相同的 RSA 模数 N 下进行 RSA 加密的 , 那么就可以恢复它们

攻击条件 :

  1. 同一模数
\[ n = pq \]
  1. 同一公钥指数
\[ e \]
  1. 两条明文存在线性关系
\[ m_2 = a m_1 + b \pmod n \quad (a \neq 0) \]
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
import libnum

n =
a =
b =
c1 =
c2 =
e = 17

def compositeModulusGCD(a, b):
if b == 0:
return a.monic()
else:
return compositeModulusGCD(b, a % b)

def franklinReiter(n, e, c1, c2, a, b):
R.<X> = Zmod(n)[]
f1 = X^e - c1
f2 = (a*X + b)^e - c2

g = compositeModulusGCD(f1, f2)
constant_term = g.coefficients()[0]


m = (-constant_term) % n
return m

m = franklinReiter(n, e, c1, c2, a, b)

print("恢复出的明文数值 m =", m)
print("-" * 50)

try:
plaintext = libnum.n2s(int(m))
print("解密后的字符串是:", plaintext.decode('utf-8'))
except Exception as e:
print("将数值转换为字符串时出错:", e)

14.CooperSmith

CopperSmith 可以用于求多项式的小根,经常用于 RSA 攻击中“已知某些二进制位,求剩余位”这一类问题

应用场景:

对于给定了一个e阶的多项式f:

\[ 1.给定β,快速求出模某个n的因数b意义下较小的根,其中b ≥ n^{β} ,(0 ≤ β ≤ 1) \]
\[ 2.在模n的意义下,快速求出n=\frac{β^2}{e}以内的根 \]

那么高位攻击明显是可以根据第二点来实现的

先对使用的函数进行介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PolynomialRing :构造多项式环

Zmod(n) :模运算

implementation='NTL' :执行 NTL

small_roots( X=None , beta=1.0 ):计算多项式的小整数根

small_roots(X = ,beta = ) 有两个参数

X代表所需要求解根的上限;虽然是根的上限,并不是说上限越高越好,当上限超过某个值的时候就会计算失效,即使已知二进制位数满足条件,也无法用此函数求得结果;所以一般来说X取在给定情况下的最大求解上限

beta即是前面提到的β ,当p,q二进制位数相同时一般只能取0.4 0.40.4;如果p,q二进制位数不同,就按照之前的方法具体问题具体分析

其中的参数:X —— 根的绝对边界

(程序默认值是 1.0 ,此时 p=N)

monic():用于将多项式的首项系数归一化为1。它接受一个多项式作为参数,然后返回一个新的多项式,其中首项系数已经被归一化为1。这个过程可以简化多项式的表达式,使其更易于计算和分析。

1.已知p高位(MSB)

把未知低位当成小根

设你已知 p的高 L位,未知低t位

  • 令已知高位拼出的近似值
\[ A = (\text{msb})\cdot 2^t \]
  • 则真素数可写为
\[ p = A + x,\quad 0\le x &lt; 2^t \]

这里的x就是未知低位,它是小的

那么构造一次多项式:

\[ f(x)=A+x \]
\[ 找到 x 使得 f(x)\equiv 0\pmod p(因为 A+x=p 被 p 整除),找到 x 后:p = A+x,\quad \gcd(p,N)=p,\quad q=N/p \]

攻击条件:

\[ 至少要知道𝑝的\frac{N位数}{4}个高位 \]

例子:

N是 1024-bit → 要求 t<256(未知低位 <256bit)→ 你至少知道 p 的高位 512-256=256 bit

N 是 2048-bit → 要求 t<512 → 至少知道 p 的高位 1024-512=512 bit

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

e = 65537
n =
c =

p_high =

PR.<x> = PolynomialRing(Zmod(n),implementation='NTL')
f = p_high + x
x0 = f.small_roots(X=2^256,beta=0.4)
print('x0 =',x0)

p = p_high + int(x0[0])
q = n//p
assert p*q==n

d = invert(e,(q-1)*(p-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

封面来自fjsmu(ふじしむ)