RSA #
基本模运算及算法 #
模运算是指取模运算，即求m/n的余数
例如：
7 mod 3 ≡ 1 -------> 7 / 3 = 2 ......1
交换律
(a + b) mod m ≡ (b + a) mod m
(a * b) mod m ≡ (b * a) mod m
1
2
3
2
3
结合律
[(a + b) mod m + c] mod m ≡ [(a + (b + c) mod m) mod m]
[(a * b) mod m * c] mod m ≡ [(b * c) mod m * a] mod m
1
2
3
2
3
分配律
[(a + b) mod m * c] mod m ≡ [(a * c) mod m + (b * c) mod m] mod m
(a + b) mod m ≡ (a mod m + b mod m) mod m
(a - b) mod m ≡ (a mod m - b mod m) mod m
(a * b) mod m ≡ (a mod m * b mod m) mod m
a^b mod m ≡ (a mod m)^b mod m
1
2
3
4
5
6
2
3
4
5
6
模运算律
a ≡ c mod m
b ≡ d mod m
a + b ≡ (c + d) mod m
a - b ≡ (c - d) mod m
a * b ≡ (c * d) mod m
a / b ≡ (c / d) mod m
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
费马定理
如果p是素数，a为正整数且不能被p整除
a^(p-1) mod p = 1 mod p
(a^p * a^-1 * a) mod p = (1 * a) mod p
a^p mod p = a mod p
1
2
3
4
5
2
3
4
5
欧拉定理
对于素数p
ϕ(p) = p - 1
对于素数p^t
ϕ(p^t) = p^(t) - p^(t-1)
例如：
90 = 2 * 3^2 * 5
ϕ(90) = ϕ(2) * ϕ(3^2) * ϕ(5)
= (2-1) * (3^2 - 3^1) * (5 - 1)
= 24
如果 m>1 a与互素
a^ϕ(m) ≡ 1 mod m
例如：
m = 11
a = 2
(2,11) = 1
ϕ(11) = 10
2^10 ≡ 1 mod 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Fermat大定理
当 n > 2 时
x^n + y^n = z^n(没有正整数解)
1
2
3
2
3
欧几里得算法
欧几里得算法又称为辗转相除法，是为了计算两个数的最大公约数。
定理：gcd(a,b) = gcd(b,a mod b) (a > b)
证明:
假设 a>b
a = k * b + r ------> r = a - k * b -----> r = a mod b
对于充分性：
假设d 为 a,b 的一个公约数，即d = gcd(a,b)
则 a | d, b | d (a与b都能被d整除)
r = a - k * b ----> r | d 即 d = gcd(b,r)
对于必要性：
假设 d 是 gcd(b,a mod b) 的公约数 ----> b | d , r | d
因为 a = k * b + r 则 a | d ----> d = gcd(d,b)
由上得知 gcd(a,b) 与 gcd(b,a mod b)公约数相等，所以最大公约数也相等
辗转相除到最后，gcd(x,0) = x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
欧几里得算法c语言代码
int gcd(int a, int b)
{
if(b == 0)
return a;
return gcd(b, a % b);
}
int gcd(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;//当a<b时第一个循环交换他们顺序
a=b;
b=r;
}
return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
模幂运算
31^52 mod 33
ϕ(33) = ϕ(3 * 11) = ϕ(3) * ϕ(11)
= (3-1) * (11-1)
= 20
53 = 20 * 2 + 12
31^53 mod 33 = 31^12 mod 33
模平方计算
31^1 mod 33 ≡ 31
31^2 mod 33 ≡ 4
31^4 mod 33 ≡ 16
31^8 mod 33 ≡ 25
31^12 mod 33 ≡ ((31^4 * 31^8) mod 33) mod 33
≡ (16 * 25) mod 33 ≡ 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
扩展欧几里得求逆元
若 mx ≡ 1 mod n, 则称m关于1模n的乘法逆元为x。也可表示为mx ≡ 1 (mod n)。逆元相当于数论中的倒数。
条件：
只有当gcd(m,n) = 1时,m 才有关于 模n 的逆元。
方法一:
利用费马小定理
a * a^(p-2) ≡ 1 mod p
a^(p-2)即为a关于1模p的逆元，但只能求出p为素数的情况下的乘法逆元
方法二:
采用扩展欧几里德算法来计算普遍情况下的乘法逆元
由 mx ≡ 1 mod n
推出
mx -kn = 1
a * x mod b = 1
ax + by = gcd(a,b) = 1
令a=m,b=n
所求出x即为逆元
加上x = (x mod t + t) mod t 即为最小逆元
为什么可以用扩展欧几里得求得逆元？
因为ax ≡ 1 (mod p) 就是ax-yp = 1.
把y写成+的形式就是ax + py = 1，为方便理解下面我们把p写成b就是ax + by = 1。
ax = 1 - by -----> ax = 1 mod b
by = 1 - ax -----> by = 1 mod a
就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得定理求值
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
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
欧几里得c语言代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,p;
int exgcd (ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd (b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
return r;
}
int main()
{
scanf ("%d%d",&n,&p);
for (int i=1;i<=n;i++)
{
ll x,y;
exgcd (i,p,x,y);
x=(x+p)%p;
printf ("%d\n",x);
}
return 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
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
RSA加密解密过程 #
因为文字太过晦涩难懂，下面以图示的方法来理解RSA加密解密的过程
以上过程中因为HACK无法得到p,q信息，也就是无法计算出d , 导致了无法解密 c 得到 m
(n,e) 公钥
(d,n) 私钥
(p,q,n,e) 生成的加密必要信息
必要的公式
c ≡ me mod n -----------> (信息加密) m ≡ cd mod n -----------> (信息解密) ϕ(n) = (p−1)∗(q−1) ----------> (n的欧拉函数) d∗e ≡ 1 mod ϕ(n) ----------> (计算e关于ϕ(n)的逆元)
RSA攻击破解 #
以下的题型全部整合在了团队的CTF平台中
Wgpsec CTF狼组平台 (opens new window)
思路 #
按照上面的流程图，可以得知，只要能知道一些关键信息就可以通过公式计算得到密文
关于RSA需要用到的几个python模块
pip install gmpy2
pip install pycrypto
pip install primefac
pip install libnum
1
2
3
4
2
3
4
分解n的网站和工具
在电脑上使用python的Crypto.Uyil.number模块中的getPrime随机生成两个128bit的大素数p,q，并通过n=p*q计算n
(isPrime是检验是否为素数)
p= 225417198511295800501004338813439346647
q= 235176424117170170684511636759421466507
n= 53012810680396841592836580182308344585066030484946806258181093403160673252029
1
2
3
2
3
假设我们没有得到p,q，拿着得到的n去yafu或者网站分解
得到了p，q的值，这样就很轻松的能得到密文了
直接模数分解N #
例子题目
有手就行-2💁♀️
c = 34533624647193630459864898193867716746457242698156942414136896826169638045191
n = 38915622445322594788113853812230848083133274092845339659216148461050062802771
e = 65537
1
2
3
2
3
我们在这可以得到c,n,e的信息
可以发现n的值并不是很大，我们使用yafu分解n值
得到了q,p的值为
q = 210984885740565358250291732634631217851
p = 184447441856923584506972548629664462921
1
2
2
在通过RSA的解密算式解密就行了
我们只用通过p,q，求出ϕ(n)
通过ϕ(n)得到私钥d,解密一下就是m的内容了
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
import gmpy2
import libnum
import hashlib
q = 210984885740565358250291732634631217851
p = 184447441856923584506972548629664462921
c = 34533624647193630459864898193867716746457242698156942414136896826169638045191
n = 38915622445322594788113853812230848083133274092845339659216148461050062802771
e = 65537
n_ol = (p-1) * (q-1)
d = gmpy2.invert(e,n_ol)
m = gmpy2.powmod(c,d,n)
print(libnum.n2s(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
费马分解和Pollard_rho分解 #
因为p,q的位数太小了，导致了yafu很容易的分解出了p,q
但是即便p,q的计算结果n非常的大，如果生成的p,q的差值过小也会导致被爆破
费马分解原理
n = p * q ---> p,q都是大素数,奇数
所以存在 a,b 有这样的关系
a = (p + q)/2
b = (p - q)/2
n = a^2 - b^2
所以只需要枚举大于n的完全平方数，即可成功分解n
当然这里出现的原因是因为p,q之间的差值过小
导致b = (p - q)/2值较小，就可以快速分解n
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
Pollard_rho分解原理
通过某种方法获得a,b
计算 p = gcd(a-b,n)
直到p不为1，或者a,b出现循环为止，然后再判断p是否为n
如果 p = n,那么返回的n是一个质数，否则返回的p是n的一个因子
紧接着递归计算 Pollard(p) 和 Pollard(n/p)，这样就可以计算n的所有质因子
1
2
3
4
5
6
2
3
4
5
6
这里我们只需要了解到分解n的原理和条件就行了
这几种方法在yafu中已经可以轻松实现
公约数模数分解 #
例子题目
不上网的好兄弟🥦
e1=65537
n1=824309976713255040678774414315188911324305343946939068909416612709427405647590959202342069019687909827092434444738101792679253192217384554228922429405912765227299967576480004693502002706412618405848902047952249003683180646566555226980812871255985212785459728851482116385274886923030294336883118688943249637504111890941209117072125746914179382718841738938542647288128064878216596964710061943380933923317756767868900496106852496453030519617669299982705549374229502330525781052290174942572613344201021252879326095620935532484506572612967292839330025773029359908312962614731172968139177410904955609738349904997096375511564814382685053981249781750176436863678070180664579983017200009530939815220400486376740060465859081480696946249903279025539697834581358967123153969680757041410395146786259547823312557522601991424424780515118072828799902432329203842554206968777062590538956711084620951141331083100850610394090226480405466880324484810299761769275660553824905489329036439444269606193857756472844072315538452095272865161396795572965527449721108417342506231371917632592432396627440113643668181341007626924926752996257541349928107829776244387124514376067059436403317102173969866403920047378658985491771106094848218483420872665866345564496827
c1=619914776107204299421445515173752551578219512744832453386701408956131174382320293166571812398142061624071844793902243230988065164689738932213640598607827763120716664826659348935506492768840667618225389848502303543184323923750014314468273838436900100602616360301578680417070089037669208417514209496064782776638328659280595442584379339709690595064375146973041893766612952550104106304945793198707913036776562970941681277387345166363055403617979919206215550071922838408131362316374998986152131970583571257394242002989402779457115646413931644663555330819307049576617764087014494844129906098270686406058331758868723651041516567453323769768954687687202307774567305854473941230877789037414544400622116272774149579612412707977679341464711326395329328746997671371678549747416132575437991623923520089934467780767741968218870533906551561755021778559582638320070802534402702441689980582215813996309661425381981953031455267480573603282477682645039060338023983236132572154559608798674661049316746566458858853902292172161686826090441354261889811244610252422433735484707855667726547016802906293840413275921015090833094030889513775808522094907659133321728552859456301911921882441570565302485792013026978232768832198065043569203133298692101550276793242
e2=65537
n2=905589252405843373769915380293297111534760160714737080968066656272265067237261488456971858456917989327188732044692331992189086519820435633306176464411261896021205034205490970644012401822191880790030875680376477319350989208508591406379353590606990790187262655027873609762696926884097121412806124968361945732028625146592611563133972373222186510357547047870461524686536342088980414561620202107652793943447542030500100100438546978201140485266000991269033918263304132180594282910120350517431177243383393951480422824952551390879069092986257009179295057946730605973160346524195449500021703749379427308594689270698548425547616170119689641602115020951172647164330653185839148908281150010508830578946902028400175833666756810132914706574636302946981088249485384995123961868977200184192366871488238130493276320548228987765469367680884015794318055385681062658024380060853629777987397931994453740025625110420802340709951010187420093537470088728911794883713099533087772597248823814645583216509715894593709142551596518622892980794670674353243620390795154580419812174256794942916769770550059026084217681241980763703393095418708693297369255695621169620925250022220663830988716484961599451891633153226183322921970730586750473413763286928431026521685503
c2=673931551637686573733931629946259955273050809105413358970865200931337620800601472110603043036230330369308198862836020608370123474012622263062171294537227742055596124838615523641277612651513376399422388728998723881390750022802888924469874997383403315092150360404739350111053494140814081500234944823944838342851486117828948012785473829786919168505899092926364319233270563625167199627187969831097779544020398227294075980803974781408640110508283074795045029934267450514279868306481527002838558049458432355280575187364797865249444744186956192622171429969229590383633312442290257337521345975778920638983724068169611670153900548976779043697802190755538297452687741381067668713313038012240461367852752324450730890453516495687244181415711446356025503068925532832441729497205951722171806849453544384230181139694995076734472488950052672657187723121538897634719634849656096065795251013915979636071103988880297602168171474689743253367371894201376237227289251967333720190335216940010089300129979229084907563995802063939925492798235466279747474279314734378363118765257958698347531646918232605837643662036855703017542230709453864001404693532353827244434156882808171822447915265832615174700571049925710515965628161428609658333071907595502748554057056
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
如果在信息传递的过程中，不小心在两次通信中生成的大素数有一个是相同的，那么就可以通过计算n的公约数来求密文
举一个小例子
n1 = 21 n2 = 27
p1 = 3 p2 = 3
q1 = 7 q2 = 9
1
2
3
4
5
2
3
4
5
通过 gcd(n1,n2) 求 n1,n2的公约数为 3
再使用公式
q1 = n1/p1
q2 = n2/p2
1
2
3
2
3
就可以得到p,q的值了
接下在就行简单的解密过程了
from Crypto.Util.number import getPrime
import gmpy2
import libnum
e1=65537
p1=29008261717768474732906182649544179950245731333856747822738033258581069736557764859442064091137212340680268427765919841814967050794545225995389669474019775859945436546756236044499372530353003845881686675641839555639930200984860821453188112209554136400254884598545226639935680295845162244784506051553763186071719627985082234455247206581278772200229668817768329850670949599442836344094584680854657993521481101663964847428180681244543566290820854582896400157941001341667919766167231693578862015420077985863396707106766463482770702693985545871194934489250728689808073962247463444300011793100734752341705797978671216386783
q1=28416386501654430231634023011382380906765239866990399332431436340108491064711397713237567536296763666523646628356952301922895839797701232191691037574805309021987595282658712896258188715354825289682378642085500458887832617987265563703665762071475093524818948426458703480477759743929208116927981543222603237052735985771173613152943586906535242363863845503107606569979697961597315510194369897277252404678573252886606721258047776336698313722607174171682001084242086119017366968245890650225737466861293317900336322062217879889573106431966815073236137390496996913378630736551144302472127942702441992143356658213344341333669
n1=824309976713255040678774414315188911324305343946939068909416612709427405647590959202342069019687909827092434444738101792679253192217384554228922429405912765227299967576480004693502002706412618405848902047952249003683180646566555226980812871255985212785459728851482116385274886923030294336883118688943249637504111890941209117072125746914179382718841738938542647288128064878216596964710061943380933923317756767868900496106852496453030519617669299982705549374229502330525781052290174942572613344201021252879326095620935532484506572612967292839330025773029359908312962614731172968139177410904955609738349904997096375511564814382685053981249781750176436863678070180664579983017200009530939815220400486376740060465859081480696946249903279025539697834581358967123153969680757041410395146786259547823312557522601991424424780515118072828799902432329203842554206968777062590538956711084620951141331083100850610394090226480405466880324484810299761769275660553824905489329036439444269606193857756472844072315538452095272865161396795572965527449721108417342506231371917632592432396627440113643668181341007626924926752996257541349928107829776244387124514376067059436403317102173969866403920047378658985491771106094848218483420872665866345564496827
c1=619914776107204299421445515173752551578219512744832453386701408956131174382320293166571812398142061624071844793902243230988065164689738932213640598607827763120716664826659348935506492768840667618225389848502303543184323923750014314468273838436900100602616360301578680417070089037669208417514209496064782776638328659280595442584379339709690595064375146973041893766612952550104106304945793198707913036776562970941681277387345166363055403617979919206215550071922838408131362316374998986152131970583571257394242002989402779457115646413931644663555330819307049576617764087014494844129906098270686406058331758868723651041516567453323769768954687687202307774567305854473941230877789037414544400622116272774149579612412707977679341464711326395329328746997671371678549747416132575437991623923520089934467780767741968218870533906551561755021778559582638320070802534402702441689980582215813996309661425381981953031455267480573603282477682645039060338023983236132572154559608798674661049316746566458858853902292172161686826090441354261889811244610252422433735484707855667726547016802906293840413275921015090833094030889513775808522094907659133321728552859456301911921882441570565302485792013026978232768832198065043569203133298692101550276793242
n1_ol = (p1-1)*(q1-1)
e2=65537
p2=29008261717768474732906182649544179950245731333856747822738033258581069736557764859442064091137212340680268427765919841814967050794545225995389669474019775859945436546756236044499372530353003845881686675641839555639930200984860821453188112209554136400254884598545226639935680295845162244784506051553763186071719627985082234455247206581278772200229668817768329850670949599442836344094584680854657993521481101663964847428180681244543566290820854582896400157941001341667919766167231693578862015420077985863396707106766463482770702693985545871194934489250728689808073962247463444300011793100734752341705797978671216386783
q2=31218321911758725262641264544273091969770000437195927621519348591685216690780159665370877797464593736322288823785921736299427583454269605453118914226531481670284475482887737160806536427086015247827565796216950059300727219056968512803067543969349155153638356001143776681725489817215982706453000587716366746160967415719391048527241185436934510948174134730584016161325490774552017155380553761311411397494107112131019774029088071262648041691040688770482053759445029125769594519046113288284952212077358169934371248462111374958967016120834878915693825454218907233538659018692509582497575166536325369627476902046824235247841
n2=905589252405843373769915380293297111534760160714737080968066656272265067237261488456971858456917989327188732044692331992189086519820435633306176464411261896021205034205490970644012401822191880790030875680376477319350989208508591406379353590606990790187262655027873609762696926884097121412806124968361945732028625146592611563133972373222186510357547047870461524686536342088980414561620202107652793943447542030500100100438546978201140485266000991269033918263304132180594282910120350517431177243383393951480422824952551390879069092986257009179295057946730605973160346524195449500021703749379427308594689270698548425547616170119689641602115020951172647164330653185839148908281150010508830578946902028400175833666756810132914706574636302946981088249485384995123961868977200184192366871488238130493276320548228987765469367680884015794318055385681062658024380060853629777987397931994453740025625110420802340709951010187420093537470088728911794883713099533087772597248823814645583216509715894593709142551596518622892980794670674353243620390795154580419812174256794942916769770550059026084217681241980763703393095418708693297369255695621169620925250022220663830988716484961599451891633153226183322921970730586750473413763286928431026521685503
c2=673931551637686573733931629946259955273050809105413358970865200931337620800601472110603043036230330369308198862836020608370123474012622263062171294537227742055596124838615523641277612651513376399422388728998723881390750022802888924469874997383403315092150360404739350111053494140814081500234944823944838342851486117828948012785473829786919168505899092926364319233270563625167199627187969831097779544020398227294075980803974781408640110508283074795045029934267450514279868306481527002838558049458432355280575187364797865249444744186956192622171429969229590383633312442290257337521345975778920638983724068169611670153900548976779043697802190755538297452687741381067668713313038012240461367852752324450730890453516495687244181415711446356025503068925532832441729497205951722171806849453544384230181139694995076734472488950052672657187723121538897634719634849656096065795251013915979636071103988880297602168171474689743253367371894201376237227289251967333720190335216940010089300129979229084907563995802063939925492798235466279747474279314734378363118765257958698347531646918232605837643662036855703017542230709453864001404693532353827244434156882808171822447915265832615174700571049925710515965628161428609658333071907595502748554057056
n2_ol = (p2-1)*(q2-1)
d1 = gmpy2.invert(e1,n1_ol)
m1= gmpy2.powmod(c1,d1,n1)
flag_1 = libnum.n2s(m1)
d2 = gmpy2.invert(e2,n2_ol)
m2= gmpy2.powmod(c2,d2,n2)
flag_2 = libnum.n2s(m2)
print(str(flag_1) + str(flag_2))
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
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
一个分解的例子 #
另一种题型，给你有关n的其他有关算式
例子：
女朋友的聊天记录🥦
题目提示：peiqi=(p+520)*(q+520)
根据给的提示分析加密过程
1,生成m的1~30的随机数次方 --->c1
2,用公钥(n,e)加密c1 --->c2
3,用公钥(peiqi,e)加密c2 --->c3
1
2
3
2
3
n=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731402197392186162426572460924170144815459280292038798573517240473723212917475994555278140089160884080770934882248855992019482512867322735936930918031567624003424284507526700957286437082738893899468444943650565398213516262653534101927337725614414267105976588592783298584640344155571836662897588729868409203459117059
e=65537
peiqi=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731572253846238252647161985685432295738082766877396752019943012580636589164644125010073946413108951305564059881537794476457602047138719485228161010739405064157783241778448944470473298163156034126054406807297456937129548816176179704045207131224909988357244665869859061263890702529905040557579134990132844969289396259
c=5482202777490716534742001860730733245703162680164829063899425154796149111749426755752696933474476315957195654145886661833161128752650489114348801850277281013599078248459234726247608999052658393093261773012085995729908722425867518715231403283837324730986276769991562455242112930535955638946020374499583285967368081356098316200877276281391326176072541717343183325729633161998105304336388217903809696260815719456619790067591554832909766088841683629739632809828420661566086443444796658031348007908713779060772794447103923388464348339614504047304444504066194611260026519898801631578959669217929301004775518173581480779628
1
2
3
4
5
2
3
4
5
构建方程
x^2-(p+q)x+p*q=0
即(x-p)*(x-q)=0 -----> 方程两个根即为p,q的值
密钥peiqi可以分解为
peiqi = p*q + 520p + 520q + 520*520
= n + 520(p+q) + 520*520
(p+q) = (peiqi - n - 520*520)//520
(p*q) = n
1
2
3
4
5
2
3
4
5
有了这些再根据求根公式计算x1,x2即为p1,q1的值
再使用 RSA 解密 2次后，爆破平方数就ok了
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long,isPrime
import gmpy2
import libnum
n=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731402197392186162426572460924170144815459280292038798573517240473723212917475994555278140089160884080770934882248855992019482512867322735936930918031567624003424284507526700957286437082738893899468444943650565398213516262653534101927337725614414267105976588592783298584640344155571836662897588729868409203459117059
e=65537
peiqi=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731572253846238252647161985685432295738082766877396752019943012580636589164644125010073946413108951305564059881537794476457602047138719485228161010739405064157783241778448944470473298163156034126054406807297456937129548816176179704045207131224909988357244665869859061263890702529905040557579134990132844969289396259
c3=5482202777490716534742001860730733245703162680164829063899425154796149111749426755752696933474476315957195654145886661833161128752650489114348801850277281013599078248459234726247608999052658393093261773012085995729908722425867518715231403283837324730986276769991562455242112930535955638946020374499583285967368081356098316200877276281391326176072541717343183325729633161998105304336388217903809696260815719456619790067591554832909766088841683629739632809828420661566086443444796658031348007908713779060772794447103923388464348339614504047304444504066194611260026519898801631578959669217929301004775518173581480779628
pq = n
paq = (peiqi-n-520*520)//520
a=gmpy2.mpz(1)
b=gmpy2.mpz(-paq)
c=gmpy2.mpz(n)
i=gmpy2.mpz(gmpy2.iroot(b*b-4*a*c,2)[0])
x1=(-b-i)//2
x2=(-b+i)//2
p1=x2
q1=x1
p2=x2+2
q2=x1+2
n1_ol=(p1-1)*(q1-1)
n2_ol=(p1+520-1)*(q1+520-1)
d3=gmpy2.invert(e,n2_ol)
m3=gmpy2.powmod(c3,d3,peiqi)
d2=gmpy2.invert(e,n1_ol)
m2=gmpy2.powmod(m3,d2,n)
for i in range(0,30):
try:
print(i)
m1=gmpy2.iroot(m2,i)[0]
print(libnum.n2s(m1))
except:
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
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
#加密方式
import random
import libnum
rand = random.randint(0,30)
m='peiqi'
m=libnum.s2n(m)
c1=m**rand
c2=gmpy2.powmod(c1,e,n)
c3=gmpy2.powmod(c2,e,peiqi)
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
小指数明文爆破 #
在一般的信息传递过程中e取值为65537，又时如果e的值过小
且满足m很小，n很大，e很小
就会出现
m^e < n
根据 c=m^e mod n
得到 c=m^e
例如
e = 3
n = 29
m = 3
c = 3^3 mod 29 ----> 3^3
也就是 c=m^3,直接开根号就会得到m
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
如果m^3 > n 且并没有超过 n 过多
存在式子
k*n < m^3 < (k+1)*n
例如
e = 3
n = 26
m = 3
c = 3^3 mod 26----> 1
k*n + c = m^3
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
这里拿平台的一道例题来理解一下
密码学表白🙆♂️
c= 70648271870529018298808886692660001235938402498859964208263409228294415956391386882206991779337601969468744143154220156908990882519717884837945906532856617909820634715854106067161582726782479804159872876992853415864029799581913231177768699278743865744051081912845185335254212638849627195499382733556635858876295634685104897939348828134359144172975276459715762939123096110061586424369639959775521808682889540769193855829876997008128536903490299132154510356729022499408881154087899262032022855765099359626306072450220026018989683836905274747226301294492449246981491703637969852470324929139841720904168369016701475473723817222435805118280228349995037458691540317562924025604518558871782328127664484684356019553232422829444404192009366087224101978739443672545344658651273357576407371982381712751927195093709853829098510072742432249637952525032152431697014721551432098156200586978917577793422057597440719114480618877894616871959869916614058028831275788375950733806459764284840487325149337299990855084479898075589047172548147875475208055116347806096743889904780424630991082111584954172971348812743549982114088569643724870601775753587500487587232004365616342285254951215710149051425199567406281845437620161540582331552889378213717815240687946879147182009028055465175524929611814188527384223348841689860466118240991278594716972892815411269840685462905179556339480041379983668015257914037862901765474982683391249869954470639078475799966417324353131574185612380759323772536955664969364984771648781609746891888279115194051967522808187234763670188472064410745331155700030125511119592595872233060513965829818176890051306809753236542584083528178867508482630064114676825193611148863808117676651877021193525941919029447722940424850259638483259618630908803708352705413985045710677257866844109324594946057235660716032547419296152445756960506166306142244870597217375420785364387192306982268095293440397581098253894684144767233449993257607977934129268826833178031802975929524501934934571709387124594721454624740923550910142337887938218289407086085953807593009004062815408946161107775999354280866956654098094276407491110119245931585538677207353167309009711825693274002853552686144987620601712501856763042883463793285988502606582149509061672725832529050936604314856886070993609898668742138501623378819838961657769663146089896801201156992228867361774391692716488518726007591552311991840025005427255145632627726384869513359648324145841090361264259057089609185017730717955467211726509629
1
2
2
这一题里面只看到了c,并没有看到其他的线索
看一下题目提示
你终于鼓起了勇气向女神表白了,但是女神的密码学tqllllllll
🤵 : aV9sb3ZlX3lvdQ==
🤹♂️ : 7064827187052901829880.........
🤵 : 😐
🤹♂️ : 等你搞清楚RSA的 c = m^e mod n 你就知道了
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
这里提示 c = m^e mod n
可以猜到这题只能是刚刚讲的小指数明文爆破了
根据 m^e < n
得到 c = m^e
编写程序爆破e就行了
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long,isPrime
import gmpy2
import libnum
c=7003953316963512304871139095211587993231123079291276945893763719959022240323069861041889815470643001299144947906274214388649617226033483962907980966853900663707585777649029162126238584277221873896766269480082618794525046351292909945659944292239052902810926099687167064811308033422459878461718134674002794768012891191252372328863603097947733980803194086307439598740909206593761856769699411851492692178913409032787606966067770304577962207797482307447844609835379279861719221580965045441176112832476043909330229525987723381894539303624464852545509270859918281262716949347750758972067923083236412130627905223127205142891163614768682817975295680866670405407880188855880293550321473460862230334726201421803013928471811099805692874844439391901456256276080565719981113677564845163001177683109687874157233055585508685647723265350544758428813903168728441549480759211100253407150847147382204992321123361503291604382645174487172534780978245775544538142604124222495493710060567737833161772359866283722481235261956476301455855983034142876174625258145548881077378791457711002290893942609172083708624223985585277312269238430952655386545189064168555461372116400801528354776128989477399459824001155917788308808042846810679642130604601568375010115916215813791441796821302353449671679062548523950749139607284358759827951717130878998700655308049733817036632749643751688935798198565174419801968716714776979226954509048678843207860410626556815809113831844395492582651269999193028511021985235012725795056131092156086021943624679453475385808194450775990758459892919126722634096576404595530275737735351801468718889436545645773134234604771827253235835754394477464047353224103053451153593127784790714628053776006414035734003004034989658814088119155665409072397248919342545815133560011673719564110407250894232179249650236390874948360250438719165497109572081139490306201401312343273868584103057978764726955782874768654917837185121357706391927294706177352964396082214488571931801912011605313211221931849029564918957272107516639099748929805640115760421342978166507444649756183189506298417295578158674520937821373129304044849974615924293291353698024515263022400465589696649352245838506359590305510294609046869715367191484039429315726474125636140119490583036055026146203364697125987090473653107687491340392043693998450421007886343014982214578894366636829436256595539986254228541
e=1
while True:
try:
if(gmpy2.iroot(c,e)[1]==True):
print(libnum.n2s(gmpy2.iroot(c,e)[0]))
break
e=e+1
print(e)
except:
e=e+1
print(e)
continue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19