rsa加密原理

  • 明文为m，密文为c
  1. 找两个质数p、q
  2. 计算n=p*q
  3. 计算n的欧拉函数φ（n）=（p-1）*（q-1）
  4. 公钥e，要求1＜e＜φ（n），且e为整数，还需要e、φ（n）互质
  5. 确定私钥d，d要满足e*d除以φ（n）余数为1
  • 加密

密文c，c=me(modn)密文c，c=m^e(modn)

  • 解密

明文m，m=cd(modn)明文m，m=c^d(modn)

解密rsa关键

  • 公开传播的是：n、e、c

  • 解密要用到：n、d、c

  • 所以rsa解密的关键就是要得到私钥d

  • 要得到d，需要通过e*d除以φ（n）余数为1

  • 在求d之前就需要求φ（n）

  • 而φ（n）=（p-1）*（q-1）

  • 所以解密rsa的关键需要求p、q

  • n = p*q，可以通过分解质因素来对p、q进行爆破（当p、q比较小或者p、q比较接近的时候是可以分解的）

rsa题型大全

基础题型

直接套公式

题目1

1
2
3
4
p = 1325465431
q = 152317153
e = 65537
计算出d,将d用MD5加密后包裹NSSCTF{}提交
  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import hashlib
p = 1325465431
q = 152317153
e = 65537
n = p * q
phi_n = (p-1)*(q-1)
print(phi_n) # 201891119372055360
d = gmpy2.invert(e,phi_n) # 这里注意，e和phi_n的位置不能调换
print(d) # 43476042047970113
print(hashlib.md5(str(d).encode('utf-8')).hexdigest())
# 08bb8fb628da85923e5734a75ac19ffe
# NSSCTF{08bb8fb628da85923e5734a75ac19ffe}

题目2

1
2
3
4
5
6
7
p=0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f

q=0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061

e=0x10001

c=0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6
  • exp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
import gmpy2
p = 32968350940699980657930803613151404473574304024691423777313774889908862596593974505408563479347203657944730457083838853799946370868164530123853574071511042506373967 #0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f
q = 2880152120462299039547844713611759800616693058487756771628124899159366904931022178508385592572818981251437302744086103000323987445642079008931937 #0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061
e = 65537#0x10001
c = 79200636304478271014515653428599205348546363880946576416664212880828226632721700716018261410389126930860598324371523316772928996360356422063555113754727289043115498759013305194277072343492062380609722125010442330717505742205680602598802403784826674446752282126860193320062982428054987016007285150027446362806#0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6
n = p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
m = int(m)
print(m)
flag = libnum.n2s(m)
print(flag)
# b'\x02\xd3\xe4v\xea\x80r\x83\xda\x99\x88\xf5#\x08\xbbAT\x8b\xaf\xd2\xf4\xdc\x9f\xd3\xbf\xb7A\xc3\xcc\xc5`\xa1\x8b\x86\x18y\xd0&\x88\x10\xef\xbe\x83\xcer\xceC\x17\xec[\xb7%\x08\xef\x16\x1f\xab\x0c\x96\xa3\xdc N^\x8e,\xa3\x11{\x99U\xcd\x15o\xd7B\xf4L\x8f}&\xc5$\xca\xd5;\xf9\x02Y\xc1\xbbS\xfd4\x83M\x96\xa9\xbd;\x83/\xf7\x00afctf{R54_|5_$0_$imp13}'

题目3：逐个字符加密

1
2
3
4
5
6
7
就你小子是黑客？
我忘记怎么解密了！
靠你了，大黑阔！

(536970330703, 65537)
message: 473878130775 40132555282 40132555282 94619939727 72818765591 208015808884 42561234694 159353248388 27748063975 159353248388 159353248388 278953790403 410746718603 496849210942 27748063975 142521857906 103632267191 17774494147 328684046745 278953790403 129956887006 129956887006 366275425558 328684046745 142521857906 410746718603 142521857906 129956887006 379067009467 328684046745 159353248388 366275425558 129956887006 103632267191 27748063975 27748063975 17774494147 160623996897 278953790403 182341799525

  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
message=[473878130775,40132555282,40132555282,94619939727,72818765591,208015808884,42561234694,159353248388, 27748063975, 159353248388 ,159353248388 ,278953790403 ,410746718603 ,496849210942 ,27748063975 ,142521857906 ,103632267191 ,17774494147 ,328684046745, 278953790403 ,129956887006 ,129956887006 ,366275425558 ,328684046745 ,142521857906 ,410746718603 ,142521857906 ,129956887006, 379067009467, 328684046745 ,159353248388, 366275425558 ,129956887006 ,103632267191, 27748063975 ,27748063975 ,17774494147 ,160623996897 ,278953790403 ,182341799525]
p=540961
q=992623
e=65537
n = q*p
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
for i in message:
    m = pow(i,d,n)
    print(chr(m),end="")

p、q可爆破

  • p、q由于位数太小，可以爆破出来。
  • 在线爆破网站：factordb.com
  • yafu爆破程序

题目1 (n较小)

  • 题目来源：
1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 65537
c = pow(m,e,n)
print(n,c)
# 62193160459999883112594854240161159254035770172137079047232757011759606702281
# 17331436837911040930486942133359735652484926528331507431552667656734821231501

image-20240417222626434

  • exp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2
e = 65537
c = 17331436837911040930486942133359735652484926528331507431552667656734821231501
n = 62193160459999883112594854240161159254035770172137079047232757011759606702281
p = 265147241000574873803071047177766359643
q = 234560843346150602519484260867514743467
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
m = int(m)
flag = long_to_bytes(m)
print(flag)
# NSSCTF{Welc0m3_t0_7h3_RSA_w0r1d}

题目2（n较小）

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

def gen_prime(nbits, gamma):
    g = getPrime(int(nbits * gamma))
    alpha = 0.5 - gamma
    while True:
        a = getRandomNBitInteger(int(alpha * nbits))
        p = 2 * g * a + 1
        if isPrime(p):
            b = getRandomNBitInteger(int(alpha * nbits))
            q = 2 * g * b + 1
            h = 2 * g * a * b + a + b
            while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
                b = getRandomNBitInteger(int(alpha * nbits))
                q = 2 * g * b + 1
            return p, q

def encrypt(nbits, gamma):
    p, q = gen_prime(nbits, gamma)
    n = p * q
    e = getPrime(16)
    while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
        e = getPrime(16)
    m = bytes_to_long(flag)
    c = pow(m, e, n)
    return n, e, c

n, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c

# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

  • 分解

image-20240417224423331

  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2
n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668
p = 8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239
q = 9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
# SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}

题目3（n较小）

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

m = bytes_to_long(flag)
n  = 1
for i in range(15):
    n *=getPrime(32)
e = 65537
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
'''
n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
'''

image-20240419204305092

  • exp：
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
import libnum
import gmpy2
from Crypto.Util.number import*
n = 15241208217768849887180010139590210767831431018204645415681695749294131435566140166245881287131522331092026252879324931622292179726764214435307
c = 12608550100856399369399391849907846147170257754920996952259023159548789970041433744454761458030776176806265496305629236559551086998780836655717
e = 65537
p1 = 2151018733
p2 = 2201440207
p3 = 2315495107
p4 = 2585574697
p5 = 2719600579
p6 = 2758708999
p7 = 2767137487
p8 = 2906576131
p9 = 2923522073
p10 = 3354884521
p11 = 3355651511
p12 = 3989697563
p13 = 4021078331
p14 = 4044505687
p15 = 4171911923
phi_n = (p1-1)*(p2-1)*(p3-1)*(p4-1)*(p5-1)*(p6-1)*(p7-1)*(p8-1)*(p9-1)*(p10-1)*(p11-1)*(p12-1)*(p13-1)*(p14-1)*(p15-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(long_to_bytes(m))

题目4（n较小）

1
2
3
e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

image-20240419204934428

  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
from Crypto.Util.number import*
e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(long_to_bytes(m))

题目5（n较小）

1
2
3
4
n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
gcd(m, n) = 1

image-20240419205344670

题目6（p可由n开根）

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from flag import flag
import libnum
p=getPrime(1024)
n=p**3
e=65537
c=pow(libnum.s2n(flag),e,n)
print(n)
print(c)
#1781066779141074297846071955037887396311182371062305797790413639302252321886055189043670187843106208315282055227397316083218930657040969292641990094428330517286511511741846106485971830443788363541411679523274683568732340113625424593194464460018629545968907529693143364870519531630721083893407011154181539445417439610805148961135948617691115328261432541033785402520757881586489819563221498111411690769065511011083021336493731421274742041131952523427183184133413677315203810963447656037908287875212013900845740870561508870574734100843624059414134156975073835607712519402938132401964708681236647568922173471703538744207491065165405594141287750705055447493380970194312139898574699147098202027540057477562090764694370368571887563631557761911842054442637038169316686266784299889397326811768646649462480349219937292894824766045607723468654723947999531346474969019631500665628522355198334827965770037487344994396753505248472283247731
#1402371150275079475353867962992356093684205278224746766691813462864343871795075217989508355749642716635931824907174189358797217546624305634264458802157933311315419673854405865092102322247505412453586251582022669511221048298234732642016439123525455296325766292112758881774720932499142635136210314142144509741404827421282969081272484330382868174392651681290127032351489627054643864671335712011990584326951285867375878235135547391155357814807654366986019707719726796289990920154227959213228064918435259919697047405788311280560319520593639968900649500117511665741073545430999580686455996145426173603547052710181735901020361145546892741579951501409108067297139928103329203429485237575169217432586580425019729120741661192297552519858305628835738911159460615968385837687234565509200392302553443089729906970894661310333276852803980265040679214814192141779678148895736682538612828771031493541256243879854624644771924477873876038496224

  • 分解n

image-20240420202029296

  • 利用欧拉公式的求法，得到phi_n

image-20240420202113862

  • exp：
1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import libnum
import gmpy2
p=121216033233585299462279856144422199686140149244819402908675131452249143435823157035320400025743305736047792084067723177554239638229731651194515823556880874798950035236056266154727789682357822323822962110560589110432270068487448525123808163818606838762211746373156874518622834972063360072190758655502892772811
n=p**3
e=65537
c=1402371150275079475353867962992356093684205278224746766691813462864343871795075217989508355749642716635931824907174189358797217546624305634264458802157933311315419673854405865092102322247505412453586251582022669511221048298234732642016439123525455296325766292112758881774720932499142635136210314142144509741404827421282969081272484330382868174392651681290127032351489627054643864671335712011990584326951285867375878235135547391155357814807654366986019707719726796289990920154227959213228064918435259919697047405788311280560319520593639968900649500117511665741073545430999580686455996145426173603547052710181735901020361145546892741579951501409108067297139928103329203429485237575169217432586580425019729120741661192297552519858305628835738911159460615968385837687234565509200392302553443089729906970894661310333276852803980265040679214814192141779678148895736682538612828771031493541256243879854624644771924477873876038496224
phi_n = (p-1)*(p**2)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

题目7 (n比较小)

1
2
3
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537
  • 分解

image-20240420202700292

  • exp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import libnum
import gmpy2
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537
p = 189239861511125143212536989589123569301
q = 386123125371923651191219869811293586459
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# b'wctf2020{just_@_piece_0f_cak3}'

题目8（p、q解方程）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import *
from flag import flag
m = bytes_to_long(flag)
p = getPrime(2048)
q = getPrime(2048)
n = p * q
e = 65537
gift = 2022 * p + 9 * q + 28 * e
c = pow(m,e,n)
print(n,c,gift)
# 559013759419746202691240598235115105126834606071307611491891982898293133657843987454339580258031532272691584368719342942404675509580909313170933925796189789232538297110756754383546447669571766593521267667716779348776308179675709803388978100416839504625045239819627379469827980589668625084314985969634985583431058156810528172627873121320455715399011186280324236548934145366222271636328254497851289112650375015433741699898290781472376090171361276557886637892800404830030548291487615566596504234212554381817510798554015481259307992175226543595948798873846335558746933940683482819439715578130806800536423771482474206047548549237879025655562739463111822524633757040958223066367993671472508367287181357997804485542311011003871312708995599690715923692968372474814753669031805664070760705148563294700043336457334028810890271434599241312612447640877347296648737167576464851763570272180801042067934843953206083053874624644994067168364645748243999074053494066054657595233970985982095621265309066132852511490426399921749091156312387594448586826952283581592003247165562367202134878625798756167825941929996806801073247649667626854029875184014003650020610359836971629737204456239324237077361643697429780638179887750984791035339697744210904151734797
# 73407318923483936681380982096598838839602514018601041044571793373013418096970487001956204920233481604663088115926046001478564679328045899017826536373925483312496867862798918521256833686293905627264784839084309695013473729502056597198558911052248943918139429481528120149662544426266704140382476129564563832751550189116712164319522536680400998100426969878312141399338984622535922004572374724499994480294086487511972287034778386491943792466926044305651852709046949243652756946391206931252732067537917128777152678266816232179411054474713462051435447023851233892017069674808619784767176865947753180156093197684363218543237706358137237603822953178987601908200096630034921280599733190041134038060644827637374731999991143342404380959195318030935855850625849684867326087432054830971960076859722417639414733054394674533018860606074648324450983897579183842853010968597034663149214229791831193351337193195298921766564073265470525286769595835642479920483047959570057149110246705969802722576770273329236163660486942433423522588321736639231667766680582482974393228214947178327111783901303686854030864244720750585928819691608599558058859371899416709995780300197269497143959726959313506292966639680257096421491364629690813416340577056873916752193925
# 63829120016023768052886024054478552450378183173692549289836790500844466624984770449526584263524969873611417764466777251459739549064993441916734929304056657281688756040121378172997367361118927461471925755841160032723693319039128805185488328610549652307644061769088611063117016010827595409949224043526660999362737741312450095192593608666286680915796697255817583078927076945852260612453896867746751729217633935143780193497702898684210698859292191506586139420497299988065973759272644964857853100511651254633164029275099534568064491202987945733565755982565356202756330311841048849063747767451397616638500281324618902190280761

  • 思路
1
2
3
4
5
6
7
gift = 2022*p + 9*q + 28*e
gift - 28*e = 2022*p + 9*q
n = p*q
gift - 28*e = 2022*p + 9*(n/p)
(gift - 28*e)*p = 2022*(p**2) + 9*n
得到一元二次方程
2022*(p**2) - (gift - 28*e)*p + 9*n = 0
  • 用sage解方程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 导入需要的库  
from sage.all import *  
  
# 定义方程的系数（这里使用大数字作为示例）  
a = 2022  # a 的值  
b = -63829120016023768052886024054478552450378183173692549289836790500844466624984770449526584263524969873611417764466777251459739549064993441916734929304056657281688756040121378172997367361118927461471925755841160032723693319039128805185488328610549652307644061769088611063117016010827595409949224043526660999362737741312450095192593608666286680915796697255817583078927076945852260612453896867746751729217633935143780193497702898684210698859292191506586139420497299988065973759272644964857853100511651254633164029275099534568064491202987945733565755982565356202756330311841048849063747767451397616638500281324618902188445725
  # b 的值  
c = 5031123834777715824221165384116035946141511454641768503427027846084638202920595887089056222322283790454224259318474086481642079586228183818538405332165708103092844673996810789451918029026145899341691409009451014138986773617081388230500802903751555541625407158376646415228451825307017625758834873726714870250879523411294753553650858091884101438591100676522918128940407308296000444726954290480661602013853375138903675299084617033251384811542251489020979741035203643470274934623388540099368538107912989436357597186986139331333771929577038892363539189864617020028722405466151345374957440203177261204827813943342267854427936943140911230900064655168006402721703813368624007597311943043252575305584632221980240369880799099034841814380960397216443313236715352273332783021286250976636846346337069652300390028116006259298012442911393171813512028767896125669838634508188183665872132449627209378611413595578854747484871621804946604515281811734195991666481446594491918357105738873838860591387781595195672603413837599295741820406811488350037281442570552234328029224490061304819213907632188805510433477369971261209659228847008641686268876656126032850185493238532744667634840106153918133696254793276868025743618989758863119318057279697898137365613173
          # c 的值  
  
# 定义方程  
x = var('x')  
equation = a*x^2 + b*x + c  
  
# 使用 solve 函数解方程  
solutions = solve(equation, x, dict=True)  
  
# 打印解  
print(solutions)

[
x == (53259187766200029811445919340226223532092820398799734412814080612563391884202543393849967630987615206080966200798183652228333589905725243025127878913526311760075783400844757808412972215579547369206649454335703779126358994294335149722081855532398733050129239482408680252836377022419922431564669995782998043828530811445686627775310022155657588316350944516191150849178215156576434815268489515716649998377480943456010188053542565378537098885682405790004693565061007587903709666118741907045957551413785083578656600195061527181355865812080856610401101423263850275626827743486117170122932148534826416253906825308190980330129/674),
x == 31488299927163782375594305784598354985055343576902151378139638110290196067918972709864013036909993584566357500427488971564319756822589646977081872239028723217808372250207143372686512583814138881980368846428364451724191019810210583450208745323418623199057207740178726519465136933610452840086315545766227500114368026151391214297362847972215483754128409704386255997220347329566039222555930464490406419002226257326118774942404683970363544788642504594073256844610344691049585870560973659315882902006631997716334351866723219577903275769313404136367236735062099234386473703566068495328080598914833401280780692803508570349879
]
  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
import gmpy2
n = 559013759419746202691240598235115105126834606071307611491891982898293133657843987454339580258031532272691584368719342942404675509580909313170933925796189789232538297110756754383546447669571766593521267667716779348776308179675709803388978100416839504625045239819627379469827980589668625084314985969634985583431058156810528172627873121320455715399011186280324236548934145366222271636328254497851289112650375015433741699898290781472376090171361276557886637892800404830030548291487615566596504234212554381817510798554015481259307992175226543595948798873846335558746933940683482819439715578130806800536423771482474206047548549237879025655562739463111822524633757040958223066367993671472508367287181357997804485542311011003871312708995599690715923692968372474814753669031805664070760705148563294700043336457334028810890271434599241312612447640877347296648737167576464851763570272180801042067934843953206083053874624644994067168364645748243999074053494066054657595233970985982095621265309066132852511490426399921749091156312387594448586826952283581592003247165562367202134878625798756167825941929996806801073247649667626854029875184014003650020610359836971629737204456239324237077361643697429780638179887750984791035339697744210904151734797
c = 73407318923483936681380982096598838839602514018601041044571793373013418096970487001956204920233481604663088115926046001478564679328045899017826536373925483312496867862798918521256833686293905627264784839084309695013473729502056597198558911052248943918139429481528120149662544426266704140382476129564563832751550189116712164319522536680400998100426969878312141399338984622535922004572374724499994480294086487511972287034778386491943792466926044305651852709046949243652756946391206931252732067537917128777152678266816232179411054474713462051435447023851233892017069674808619784767176865947753180156093197684363218543237706358137237603822953178987601908200096630034921280599733190041134038060644827637374731999991143342404380959195318030935855850625849684867326087432054830971960076859722417639414733054394674533018860606074648324450983897579183842853010968597034663149214229791831193351337193195298921766564073265470525286769595835642479920483047959570057149110246705969802722576770273329236163660486942433423522588321736639231667766680582482974393228214947178327111783901303686854030864244720750585928819691608599558058859371899416709995780300197269497143959726959313506292966639680257096421491364629690813416340577056873916752193925
gift = 63829120016023768052886024054478552450378183173692549289836790500844466624984770449526584263524969873611417764466777251459739549064993441916734929304056657281688756040121378172997367361118927461471925755841160032723693319039128805185488328610549652307644061769088611063117016010827595409949224043526660999362737741312450095192593608666286680915796697255817583078927076945852260612453896867746751729217633935143780193497702898684210698859292191506586139420497299988065973759272644964857853100511651254633164029275099534568064491202987945733565755982565356202756330311841048849063747767451397616638500281324618902190280761
e = 65537
p = 31488299927163782375594305784598354985055343576902151378139638110290196067918972709864013036909993584566357500427488971564319756822589646977081872239028723217808372250207143372686512583814138881980368846428364451724191019810210583450208745323418623199057207740178726519465136933610452840086315545766227500114368026151391214297362847972215483754128409704386255997220347329566039222555930464490406419002226257326118774942404683970363544788642504594073256844610344691049585870560973659315882902006631997716334351866723219577903275769313404136367236735062099234386473703566068495328080598914833401280780692803508570349879
q = n//p
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))
# NSSCTF{S4g3_is_4_g00d_thing}

题目9（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
from gmpy2 import *
from Crypto.Util.number import *

flag  = '**********'

p = getPrime(512)
q = next_prime(p)
m1 = bytes_to_long(bytes(flag.encode()))


e = 0x10001
n = p*q


flag1 = pow(m1,e,n)
print('flag= '+str(flag1))
print('n= '+str(n))


flag= 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243
n= 52147017298260357180329101776864095134806848020663558064141648200366079331962132411967917697877875277103045755972006084078559453777291403087575061382674872573336431876500128247133861957730154418461680506403680189755399752882558438393107151815794295272358955300914752523377417192504702798450787430403387076153


  • 分解p、q

image-20240421181429106

  • exp：
1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
import gmpy2
p = 7221289171488727827673517139597844534869368289455419695964957239047692699919030405800116133805855968123601433247022090070114331842771417566928809956044421
q = 7221289171488727827673517139597844534869368289455419695964957239047692699919030405800116133805855968123601433247022090070114331842771417566928809956045093

n = p*q
c = 10227915341268619536932290456122384969242151167487654201363877568935534996454863939953106193665663567559506242151019201314446286458150141991211233219320700112533775367958964780047682920839507351492644735811096995884754664899221842470772096509258104067131614630939533042322095150722344048082688772981180270243

e = 65537
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

题目10（p、q未知，但p-q很小）yafu分解

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

p = getPrime(1024)
q = next_prime(p)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(f"n = {n}")
print(f"c = {c}")

"""
n = 19421904767367129549329507820147867763064747101931314714173717122035977491291441314433180813343755107381230481007143328156292096871675328839756035726106037229325380698967544660649710464634698425387682458721466040894830503881966355435442651493212040443436714597490121865537266815247879839020846287255634123530517095030752832857842819836940083915495464712363169428825344678729929317207583197980607919720642725221740680718976635305544368542563503440076036727388062097647374046378854873864505267644315352602271587283702733779081805129429479541906613334092422428543951370065910195162721686773383508480268145903016615151713
c = 16430654037742749931837577925393394466626615745270895225352757745284038922799868617243616416116392338428121605256850230862894296244375242336599929497221079420665154174930054597666915358687410522457846003186806053368237783147731665147575913322026626738697036282908055611350347494310666532700194563684837580022875526378181343082801716942536163583090541294011987732281942148455345223347021675781368596340860151253774597168954881987520338304516390785094435356412111780768446904948045448510663589654475221029009283144829902553888829840193614048967712676048740814622290029846433107762872806981599110271586325156855299974310
"""
  • 分解，这题在线网站分解不了，使用工具分解
  • 命令分解.\yafu-x64.exe "factor(6)"

参考博客：[Yafu、gmpy2安装及使用 | YLCao’s Blog](https://ylcao.top/2021/06/05/yafu、gmpy2安装及使用/#:~:text=yafu 用于自动整数因式分解， 在 RSA 中，当 p、q 的取值差异过大或过于相近的时候，使用 yafu,processing batchfile 。 运行命令： .\yafu-x64.exe “factor(@)” -batchfile data.txt)

  • 由于该数过大，需要线创建文本，将要分解的n写入文本中，结尾要换行否则分解不了

image-20240421191116733

  • 然后在目录里面进入终端

image-20240421191201775

  • 然后输入指令 .\yafu-x64.exe "factor(@)" -batchfile data.txt分解得到

image-20240421191306751

  • exp：
1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
p=139362494120072096065216081618966249746574239262460284744468865719850996551067753709694109554061693572089871188264746799340636786772313403025084938651609422567995344046775583983367311974802321610889005077947700976481552283896499334735377828779462799614319016720722734724022186712293418763283488943785244226387
q=139362494120072096065216081618966249746574239262460284744468865719850996551067753709694109554061693572089871188264746799340636786772313403025084938651609422567995344046775583983367311974802321610889005077947700976481552283896499334735377828779462799614319016720722734724022186712293418763283488943785244226299
e = 0x10001
n=p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
c = 16430654037742749931837577925393394466626615745270895225352757745284038922799868617243616416116392338428121605256850230862894296244375242336599929497221079420665154174930054597666915358687410522457846003186806053368237783147731665147575913322026626738697036282908055611350347494310666532700194563684837580022875526378181343082801716942536163583090541294011987732281942148455345223347021675781368596340860151253774597168954881987520338304516390785094435356412111780768446904948045448510663589654475221029009283144829902553888829840193614048967712676048740814622290029846433107762872806981599110271586325156855299974310
m = pow(c,d,n)
print(libnum.n2s(int(m)))
# flag{when_PQ_is_near_Its_simple}

共享素数

题目1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
m=bytes_to_long(b'xxxxxx')
e=65537
p=getPrime(1024)
q1=getPrime(1024)
q2=getPrime(1024)
n1=p*q1
n2=p*q2
c1=pow(m,e,n1)
c2=pow(m,e,n2)
n3=n1^n2
print('n1=',n1)
print('n3=',n3)
print('c1=',c1)
print('c2=',c2)
#n1= 9852079772293301283705208653824307027320071498525390578148444258198605733768947108049676831872672654449631852459503049139275329796717506126689710613873813880735666507857022786447784753088176997374711523987152412069255685005264853118880922539048290400078105858759506186417678959028622484823376958194324034590514104266608644398160457382895380141070373685334979803658172378382884352616985632157233900719194944197689860219335238499593658894630966428723660931647038577670614850305719449893199713589368780231046895222526070730152875112477675102652862254926169713030701937231206405968412044029177246460558028793385980934233
#n3= 4940268030889181135441311597961813780480775970170156650560367030148383674257975796516865571557828263935532335958510269356443566533284856608454193676600884849913964971291145182724888816164723930966472329604608512023988191536173112847915884014445539739070437180314205284883149421228744714989392788108329929896637182055266508625177260492776962915873036873839946591259443753924970795669864031580632650140641456386202636466624658715315856453572441182758855085077441336516178544978457053552156714181607801760605521338788424464551796638531143900048375037218585999440622490119344971822707261432953755569507740550277088437182
#c1= 7066425618980522033304943700150361912772559890076173881522840300333719222157667104461410726444725540513601550570478331917063911791020088865705346188662290524599499769112250751103647749860198318955619903728724860941709527724500004142950768744200491448875522031555564384426372047270359602780292587644737898593450148108629904854675417943165292922990980758572264063039172969633878015560735737699147707712154627358077477591293746136250207139049702201052305840453700782016480965369600667516646007546442708862429431724013679189842300429421340122052682391471347471758814138218632022564279296594279507382548264409296929401260
#c2= 854668035897095127498890630660344701894030345838998465420605524714323454298819946231147930930739944351187708040037822108105697983018529921300277486094149269105712677374751164879455815185393395371001495146490416978221501351569800028842842393448555836910486037183218754013655794027528039329299851644787006463456162952383099752894635657833907958930587328480492546831654755627949756658554724024525108575961076341962292900510328611128404001877137799465932130220386963518903892403159969133882215092783063943679288192557384595152566356483424061922742307738886179947575613661171671781544283180451958232826666741028590085269

  • 思路：
1
2
目标就是求p，利用gcd(n1,n2)
之后q1，q2就好求了
  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
import gmpy2
n1= 9852079772293301283705208653824307027320071498525390578148444258198605733768947108049676831872672654449631852459503049139275329796717506126689710613873813880735666507857022786447784753088176997374711523987152412069255685005264853118880922539048290400078105858759506186417678959028622484823376958194324034590514104266608644398160457382895380141070373685334979803658172378382884352616985632157233900719194944197689860219335238499593658894630966428723660931647038577670614850305719449893199713589368780231046895222526070730152875112477675102652862254926169713030701937231206405968412044029177246460558028793385980934233
n3= 4940268030889181135441311597961813780480775970170156650560367030148383674257975796516865571557828263935532335958510269356443566533284856608454193676600884849913964971291145182724888816164723930966472329604608512023988191536173112847915884014445539739070437180314205284883149421228744714989392788108329929896637182055266508625177260492776962915873036873839946591259443753924970795669864031580632650140641456386202636466624658715315856453572441182758855085077441336516178544978457053552156714181607801760605521338788424464551796638531143900048375037218585999440622490119344971822707261432953755569507740550277088437182
c1= 7066425618980522033304943700150361912772559890076173881522840300333719222157667104461410726444725540513601550570478331917063911791020088865705346188662290524599499769112250751103647749860198318955619903728724860941709527724500004142950768744200491448875522031555564384426372047270359602780292587644737898593450148108629904854675417943165292922990980758572264063039172969633878015560735737699147707712154627358077477591293746136250207139049702201052305840453700782016480965369600667516646007546442708862429431724013679189842300429421340122052682391471347471758814138218632022564279296594279507382548264409296929401260
c2= 854668035897095127498890630660344701894030345838998465420605524714323454298819946231147930930739944351187708040037822108105697983018529921300277486094149269105712677374751164879455815185393395371001495146490416978221501351569800028842842393448555836910486037183218754013655794027528039329299851644787006463456162952383099752894635657833907958930587328480492546831654755627949756658554724024525108575961076341962292900510328611128404001877137799465932130220386963518903892403159969133882215092783063943679288192557384595152566356483424061922742307738886179947575613661171671781544283180451958232826666741028590085269
e=65537
n2 = n3^n1
p = gmpy2.gcd(n2,n1)
q1 = n1//p
q2 = n2//p
phi_n1 = (p-1)*(q1-1)
phi_n2 = (p-1)*(q2-1)
d1 = gmpy2.invert(e,phi_n1)
d2 = gmpy2.invert(e,phi_n2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(libnum.n2s(int(m1)))
print(libnum.n2s(int(m2)))
# b'LitCTF{TH3_Tw0_nUmb3rs_H@v3_The_sAme_D1v1s0r!!}'
# b'LitCTF{TH3_Tw0_nUmb3rs_H@v3_The_sAme_D1v1s0r!!}'

题目2

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

m1=bytes_to_long(flag[:16])
m2=bytes_to_long(flag[16:])
p=getPrime(1024)
q1=getPrime(1024)
q2=getPrime(1024)
n1=p*q1
n2=p*q2
e=65537
c1=pow(m1,e,n1)
c2=pow(m2,e,n2)
print("n1=",n1)
print("n2=",n2)
print("c1=",c1)
print("c2=",c2)
'''
    n1= 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857
    n2= 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577
    c1= 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179
    c2= 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621
'''
  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
import gmpy2
n1= 18680935400842120133090782991548100098299141114788036098274292600814484762178879421175852824971602717084073867867453382415307589970440719890918576225495401632854107018246844209327118177917122236073227158593514362850629722223228335334773008682775987859295083444638923726449899310854161394586430943134469559429878238769266114132469166535509030877235272476877484918308883799496627699789051809542538091061550107526246728583019140703765888157806778516567048103700384849598143249322109207879381251223776896702362630437178664824125387477797876186939235800859102380783259361745143574493440078787931593394188675093506492640857
n2= 16308523133405725830120564525574438512803584148781960516042054284309437381876822602134185065101371986717984978566359252072738078020261823966208153922611063201149105749778596739692554295573408850719208215646167050188830459343054219856901871953140988948482577813730729085764541988120049026971705499798003225755018687242522370406495429425494022876627543617474873929054728724093702291448754458748923218635900061398716191201846139296921753782690468189409101899415028480878296408735247604084627019116374444335509072590669239349212479592499426230525792270750612371117196200786891891430446212938482959351978202358044864822577
c1= 534518909595318304521410713148076850830155521838755402438490325620155197496935820831936109252194297244161393310730073882257949954815312409974998733265641354273665213856408848764503848122264972023143474923678585167025591255034150826271791019266426616987355463111138963331008761826310757292765842789380409826387579098421126952331558360737102888876551724241978020305977032047901621477384392409864427091911872691182528938458750707982564581322551517287491916691010743390992018974168703956622998928457142606354825714033609199676987795174032254878017883605565760275857658822315970522114838062469258676628619381342357632179
c2= 10248394002302905069278122013496854496130190499518622376819239887579692634750808499513497018453473232140518824608976734237637842228035017757831938865937098325684711995382081489403971465596662585196007547659143066184546400992333479193424580690897692586491475768279754939199148642035267049092880715299621206567123356521609120801306358100326600900326310677054810032471472266402660807205675696110133573150125117412696328434523507708110949743705536889950671778501402435457354251761692098671783596194430798692942013503015764266392551048702428063161786512924608239609802040937400619384828550050291094616346317726139970219621
e = 65537
p = gmpy2.gcd(n1,n2)
print(p)
q1 = n1//p
q2 = n2//p
phi_n1 = (p-1)*(q1-1)
phi_n2 = (p-1)*(q2-1)
d1 = gmpy2.invert(e,phi_n1)
d2 = gmpy2.invert(e,phi_n2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(libnum.n2s(int(m1)),libnum.n2s(int(m2)))
# FSCTF{0hN0_Y0u_f1nd_th3_gcd!}

不互素

多个n，当n之间不互素

  • 当题目给多个n的时候，需要去求一下多个n之间的最大公因数，看看是否有不互素的情况
  • 如果出现不互素的情况那么其中的n=p*q，中的p就已经给泄露出来了
  • 剩下的就是正常的RSA解密过程了

题目1

[羊城杯 2021]Bigrsa | NSSCTF

  • 题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from flag import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)

print("c = %d" % c)

# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import libnum
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p = 10210039189276167395636779557271057346691950991057423589319031237857569595284598319093522326723650646963251941930167018746859556383067696079622198265424441
q1 = n1//p
q2 = n2//p
phi_n1 = (q1-1)*(p-1)
phi_n2 = (q2-1)*(p-1)
d1 = 52972050904698708999694860680227007394081915071135725129999780376269490232842636149391123520395046329661145954720920441679748578755580991675741897417819692207924672531636829869855389907042005657737863358015872760510068994570860695476344436093246058153047496026356252497725455415027057242991074953502219819073
d2 = 49007533390345500670821203519681632928781047694791461837384578372759254068377388498350973294154846607235580752328386730173867156981291249019429694873435288987021071863869575409656752237998953773045547840743632191085327380057520255730441098236826803802420518393344661660737818531715453426870823000127849114113
print(d1)
print(d2)
c1 = pow(c,d2,n2)
m = pow(c1,d1,n1)
print(libnum.n2s(int(m)))

e很小

直接开平方

广播攻击

  • 广播攻击涉及到的是中国剩余定理
题目1

[鹤城杯 2021]Crazy_Rsa_Tech | NSSCTF

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

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
  • 题目还给了一个文件，记录了每次rsa加密所使用的n和所得到的c

image-20240702165007823

  • 多组加密直接sage用CRT跑出m**e,并不需要9组都上，三四组即可
1
2
3
4
5
6
7
8
# 定义模数和余数
a = [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799,92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949,100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919,59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377]
n = [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585,46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900,85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198,14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981]
# 使用 SageMath 求解
x = crt(n, a)

# 输出结果
print(x)
  • 然后得到m**e最后在开方得到flag
1
2
3
4
5
6
7
import libnum
import gmpy2
flag = 3678337284039442047026947312380394506988284605153398380909870598085147736828709178219597429308046538374273111663234962853201175297522552444068549756304348183089003998584929250444862897734669616839072634559776823068102560978738392642133409979083241310818961120830565330801827594023873873703163937572703881578432281109467318674533265052430906776650900523035132668203491899352234368836316318216812572637893433384928785981896373747430646617935503364537613820302679656375356094380483213814869276308187497478084540603362678580814022322799191778371368875742773945120383365613028633102737056410926701477700008313642639347163933146129361496566648131161287075292980980083166106192999528561889437021539352391671756010617540361596164032486633114877739259434431765044242037641759566659268290619705700083536966807192023377334915872207418596226819579720241509860110741821630775501873143209229299530346706612248414951753383716954165108266753409813119293227854442685830689203424064786691447734948037502729127922328149002842971722645909768174575776908113523451541199095073733017029558396658874593357205426105429760517295964966905772455366037986657671195106462661190327510507460112791663031458690187525393979689469548319821181450874331998372947479866557921497942728807505035932385939931524294822439633516457845581452433022749099648076725811489217888688273759202726271093237450290814247396662589614216704
m = libnum.nroot(flag,9)
print(libnum.n2s(int(m)))
# b'flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16'

rsa变式

泄露之方程

  • 已知一种p、q关系
    • p-q泄露
    • dp、dq泄露
    • p^n-q^m泄露

题目1：p-q泄露

1
2
3
4
n = 24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
p - q = 14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
e = 65537
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343
  • p-q泄露直接推phi_n
1
2
3
4
5
n = p*q
p-q已知，那么（p+q）**2 = （p-q）**2 + 4*n
这样就知道了p+q
phi_n = (p-1)*(q-1)    右边展开
phi_n = p*q-(p+q)+1 = n-(p+q)+1
  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
import gmpy2
n = 24585768801100871989460458412563674690545986652089097718040761783186739174559136657307807040444318337561194142282186006216583089898423180103199568738639814413601595196467099996734334212909157604318709957690532885862891927163713619932622153281344607898846228206181834468325246573910857887714824338949742479585089251882243488454602710292507668577598274622372304293403731722318890268908300308478539449464617438721833942643889296634768118375076052778833640986893990732882252524850152650060780854621796349622086656401914022236044924841914313726991826438982902866584892213702893596657746111940812657202364588469026832387629
a = 14048479366496281701869293063643750801596179514889914988732592464154208813942939793532694949932787548745769133200541469022315588864587160064703369956054828780928008235304461825448872454098086255531582368864754318040219023548966787642948010656526691472780392631956031751285174567712974691729142190835749586660
b = a**2+4*n
pq,f = gmpy2.iroot(b,2)
e = 65537
c = 13043206753625359891696429504613068427529111016070088678736297291041435652992434742862062899975037273524389833567258051170507686131853178642412748377655159798601888072877427570380109085131089494464136940524560062629558966202744902709909907514127527274581612606840291391818050072220256661680141666883565331886278443012064173917218991474525642412407692187407537171479651983318468186723172013439034765279464665108704671733067907815695414348312753594497823099115037082352616886076617491904991917443093071262488786475411319592529466108485884029307606114810451140886975584959872328937471166255190940884805476899976523580343

phi_n = n-pq+1
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

题目2：p^m-q^n泄露

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

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(128)
n = p*q
hint = p**3-q**5
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'hint = {hint}')
'''
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
'''
  • 思路

IMG_20240421_183723

  • sage脚本
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
# 导入需要的库  
from sage.all import *  
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
n = n**5
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
# 定义变量  
a, b, c, p = var('a b c p')  
  
# 定义方程  
equation = a*p^8 + b*p^5 + c  
  
# 假设我们有一些具体的 a, b, c 的值，例如 a=1, b=2, c=3  
# 你可以根据需要修改这些值  
specific_a = 1  
specific_b = -hint
specific_c = -n
  
# 将具体的值代入方程  
specific_equation = equation.subs({a: specific_a, b: specific_b, c: specific_c})  
  
# 使用 solve 函数求解方程  
# 注意：对于高次方程，可能没有解析解或者解的数量可能很多  
solutions = solve(specific_equation, p, dict=True)  
  
# 打印解  
for sol in solutions:  
    print(sol)
p == 7321664971326604351487965655099805117568571010588695608389113791312918573783115429227542573780838065461696504325762281209452761930184231131129306271846427
0 == p^7 + 7321664971326604351487965655099805117568571010588695608389113791312918573783115429227542573780838065461696504325762281209452761930184231131129306271846427*p^6 + 53606777952351006120437890132401495889883119979363551079013047064091279231518974610584673384973960799560838292465366197008803085935988574584920077330574353334716488780542955862037081661368859004582338322399440245140416040284846085341133667539945874199266539108088620755862255546680261520976696079803872666329*p^5 + 2625702519728484185145256425722523787931835719009962652420366135463836490405634662255057409835393645941165444713429891809710716285844556747956693836997357589441939273187279655570088401145097551*p^4 + 19224514163820044957961741442664914855709579536840412058703242421103067648432111046349494723646419404973118635726200550639650346767312008655290204361565978590149544043877400325916090535051978915805069235818798510919449230614676688520713740740963844940453238262138608638430981101101440083306694739030877531914125322223998514243708090367083805800277*p^3 + 140755451944013388697499305991128559272817692899127252147469536612117358818700974206585112934722292391045683325119084031746715889441578983652531861891557529212099236280213140677151561438479190286799670841127617616956825599292024830531363692805743469275544632491668803074817026869984437179654527634577210981786971693457950131077864974678528739182827077306240228526260258538290052356156752391538263004806404420869009540372037027406172969312239848076519975309370616303436332562637127700948634129178060279*p^2 + 1030564262021728024282057991439643536315903938403642232788404589442943870494325094736937427249671104650561406616139958236450547004306571352013456535117763432075138243287969685272449801285535317730897996778861652988607800706083594672904232721626683099046300815693966053039453296259417499299087157710479815890153935125304596899742902280989853360199221205067791254156804408325410292186219522580863948560724266083935179533437484257212385104937721298659194875557683943026091772024336250710520707196475141504734540488827242373497520216547749963732712777146225394230544630888711638423070935506699239119849472023721252734337907406255779745904542358748507636773133*p + 7545446257945538488739261814223289458742925107341456621331393551500250806227231832255023639885329554443007989024266675104934587302060983324064502275878051681170158354643840880993971612911352477945399169496631598998533682044243778919967682009112457556552912825410825575934195734416035103231749176597378955710506729256714391693801818566600627675128979550310850787103427312736372829345301232223443791194835615991496324995543084294066574920999246736656940698831834339368629694376769701417407654301462731651982040584579017261222203247547224023174887469080882714176518819868211300899164294971580812273370901548130224897216251714228442164790631953716814408868089722337054292185859401100230960525890164039640800302636466939203908930350833857673884576491524684372379527407643744287689753069599307418002374688015645791

题目3：p+p×q^3和p×q+p×q^2泄露

1
2
3
4
('c=', '0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9eL')
('e=', '0x872a335')
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
  • 一眼就是解方程
image-20240619222524753
  • 利用在线sage解方程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 定义变量
x = var('x')

# 定义一元三次方程，例：ax^3 + bx^2 + cx + d = 0
a=1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
b=-1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
c=-1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
d=1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
equation = a*x^3 + b*x^2 + c*x + d == 0

# 求解方程
solutions = solve(equation, x)

# 输出解
print("The solutions to the cubic equation are:")
for sol in solutions:
    print(sol)

  • exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
import libnum
import gmpy2
p = 1158310153629932205401500375817
a = 1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
q = a//(1+p**3)
print(q) # 827089796345539312201480770649
n = p*q
e = 0x872a335
c = 0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

出现公倍数的情况

题目1：lcm(p - 1 , q - 1)

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

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 54666
trick = lcm(p - 1 , q - 1)
flag = b'FCTF{***********}'
m = bytes_to_long(flag)
c = pow(m, e, n)
print('n: ', n)
print('trick: ', trick)
print('c: ', c)



'''
n:  25527104228224088488040470054859297799684430729586201999927539150044992353999083976287914924970569469434686168557247480896928199907052200737794107820101535432772515334456482673511185210116841919416618006696356771202410487435695207310741143088507315599413718818919895412368893805095614918899139207456629111515498628424508456173008212962396577655489900115537922862725514355690650346542020236913649627901430140820374812887483132677589636744805036428604336253688728768629554430310965303561197842773841768036265483485885167914975226451364872214945774294272151759555341126251417977165442601848916571897507614450138696307441
trick:  3190888028528011061005058756857412224960553841198275249990942393755624044249885497035989365621321183679335771069655935112116024988381525092224263477512691929096564416807060334188898151264605239927077250837044596400301310929461900913842642886063414449926714852364986926546111725636951864862392400932078638939397162813314446093112008451870874459413340817966632865485406320788272316381137437957674310631802876313435533326327324210320100692584743680300917008843045504725648240011406960704841222641567549521400885041138306803979812904472944466100873729786606242613061006721938847831340052029664934674085291935568007804584
c:  13816656057233504242725466607519098922616296851282996573245636803888321169952138063011430581813327223855035775201965978271601144858474586480811825971179893352623779199435743915535990803704703901640138034283878850535619383284762202523145531803148037944606221169858890092284283768859214489478888725916054874525393017572123038563581085488781982829726844109883458439559508856073477596828594786184067989967020470472291721891068880110540699901476565507918536144452248311628215837448639176024403880919704090284307989085868140402906218076204485172179740170107661474514833980476371750724966421481356221210695767530318458804012

'''

费马小定理与rsa

题目1 GHCTF

[GHCTF 2024 新生赛]2023四省联考 | NSSCTF

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

m = bytes_to_long(flag)

def getKey():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    assert m < n
    _g = randint(1,n)
    _a = randint(1,n)
    _b = randint(1,n)
    return _g,_a,_b,p,n

def encrypt():
    key = getKey()
    _key = pow(key[0], key[1] * (key[3]-1), key[4])
    c = (pow(_key, key[2], key[4]) * m) % key[4]
    return key[4], _key, c

if __name__ == '__main__':
    print(encrypt())
    
(18179834236782025892165859358541969039672768622078317899558535972829779066590034272465041741258879770213528640616887797155080398928088158585694106907734126514213361875345507975960317351812797992725951327122851713302327820458710931182497244211627793166445441450354787055708273445176257841426295561697059359851693234672902342001564298222123930677021693824135290857682548806726262690296776413730423712555689778608531366304345258560702517364961150273435113114487840186421965955626002395362990009595593448407759619600184788649602049313701058708439962867646774483596360223764988749726613678029307186833464512585242569435003, 11847655277251446942383940882912368688156808473955941053063218251376227576794849789637061751561030423224338717881358695503734129213448747206540310077968159679087902861554101729530885006978457916005370151390141770528828726044070599163879940393777653050010384591813315879288161460396096268260181418863020260300992421872071273292678599559844166740721617200084689717099280979932276914367828947937478359933181441706805653179826272658999406454166746306193757296165968606398592219586135127604969713571323480832108309240510220649110629512108142189299294329845348146274638537031635599971704959419196082418167981085622698281250, 14415195091596957208690057717270843038813723273773797640804955509618976877138721476691508292484187601673314627535732234517837698631950684940570225175917508902812451340933203438247448893168609525426014319195770233401480816194489198464476480610373345480444974658239730190879678428967798637043230820661470572128997114218312981971051639788050332764374932384836724719743407759997343303062259374222621789562479046933232021478087932233308027796973486804634154183554333108258875955181959785332882009189939917648988868671919046698887438054678239786487480196578700573286352849560893479759745211457149133610748492277912237022560)
  • exp:
1
2
3
4
5
6
7
8
9
10
11
import gmpy2
import libnum
n = 18179834236782025892165859358541969039672768622078317899558535972829779066590034272465041741258879770213528640616887797155080398928088158585694106907734126514213361875345507975960317351812797992725951327122851713302327820458710931182497244211627793166445441450354787055708273445176257841426295561697059359851693234672902342001564298222123930677021693824135290857682548806726262690296776413730423712555689778608531366304345258560702517364961150273435113114487840186421965955626002395362990009595593448407759619600184788649602049313701058708439962867646774483596360223764988749726613678029307186833464512585242569435003
_key = 11847655277251446942383940882912368688156808473955941053063218251376227576794849789637061751561030423224338717881358695503734129213448747206540310077968159679087902861554101729530885006978457916005370151390141770528828726044070599163879940393777653050010384591813315879288161460396096268260181418863020260300992421872071273292678599559844166740721617200084689717099280979932276914367828947937478359933181441706805653179826272658999406454166746306193757296165968606398592219586135127604969713571323480832108309240510220649110629512108142189299294329845348146274638537031635599971704959419196082418167981085622698281250
c = 14415195091596957208690057717270843038813723273773797640804955509618976877138721476691508292484187601673314627535732234517837698631950684940570225175917508902812451340933203438247448893168609525426014319195770233401480816194489198464476480610373345480444974658239730190879678428967798637043230820661470572128997114218312981971051639788050332764374932384836724719743407759997343303062259374222621789562479046933232021478087932233308027796973486804634154183554333108258875955181959785332882009189939917648988868671919046698887438054678239786487480196578700573286352849560893479759745211457149133610748492277912237022560
p = gmpy2.gcd(_key-1, n)
flag = (int)(c % p)

print(libnum.n2s(flag))

# NSSCTF{F3RmM4t's_Li7tLe_The0Rem_1s_S0_Funny!}

维纳攻击

  • 维纳攻击（Wiener’s Attack）是一种针对RSA加密算法的密码攻击方法，尤其适用于私钥 d 较小的情况。它基于一种数学技术——连分数（continued fractions）——来破译RSA加密。
  • 适用条件：

image-20240830194243658

题目1 HGAME 2022 week3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime
from gmpy2 import invert
from libnum import s2n
from secret import flag

p = getPrime(2048)
q = getPrime(2048)
n = p * q
d = getPrime(64)
e = invert(d, (p - 1) * (q - 1))
c = pow(s2n(flag), e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

n = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
  • exp：
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
import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n= 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e= 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c= 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
print(n)
d=wienerAttack(e, n)
print(d)
m =pow(c,d,n)
print(libnum.n2s(m))
# hgame{dO|YOU:kNOw!tHE*PRINcIplE*bEhInd%WInNEr#aTTacK}

题目2 XYCTF Factor1

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


p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)

# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

  • 思路：
1
2
3
phi_n**3 = (p**3-1) * (q**3-1)
# 就知道了N、e可以用连分数法求d
# 知道e、n、d就可以分解p和q，然后就可以得到flag
  • exp
  1. 求d
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
import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n= 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
e= 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
c= 30443384983816710270001651296607959522389400057103143909277631290995899073895621701281106228069835965181342091582584186637031613250922961166298411359757600825556083868477673357860585539016515776933117915504873987178857740106223631465737111746470236003857656528610755145017342412306680097140732745012583119076
n=n**3
print(n)
d=wienerAttack(e, n)
print(d)
#d=8447122254265361577759220083550460887840558233627984117576685838469227480934556534673167325385487344741530262745308367064419215281251764917289925433582347
  1. 分解p、q（用Sage）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n=99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

e=172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163


d=8447122254265361577759220083550460887840558233627984117576685838469227480934556534673167325385487344741530262745308367064419215281251764917289925433582347

b = e * d - 1
while (b % 2 == 0):
    b = b /2
else:
    t = int(b)
a = 2
while (a < n):
    x = power_mod(a, t, n) - 1
    d = gcd (x,n)
    a += 1
    if (d != 1) and (d != n):
        p = d
        q = n // d
        print(d)
        print(n // d)
        break
  1. 得到flag
1
2
3
4
5
6
7
8
import gmpy2
import hashlib
from Crypto.Util.number import *
p = 10754959493573546439510276829300246769373124436128170955050379041986504869221750743052397622171703140881050431144683659643071578143360949942206693325622779
q = 9212046353930376594996890089494718736894378991991381248242532319628627449681664076081705664941905594411935750003102856235503684466394327681725704255564467
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(flag)
# XYCTF{a83211a70e18145a59671c08ddc67ba4}

泄露之位数

  • 做到这里也只能做脚本小子了。原本还想着理解之后做的，太花时间收益太少，先积累脚本等学到密码学的时候再理解吧

题型1p高位泄露

题型2p高位、q低位泄露

  • 这题是BaseCTF新生赛的一题

  • 题目附件

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 getPrime, bytes_to_long
from secret import flag
flag=b'XXXX'

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 721
hint2 = q % (2 ** 266)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
'''
hint1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
hint2 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
'''
  • exp:
  • 先使用sage求出p的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes
p1 = 14439249591349619691972392177790365247490839237199085979433418493254022567815148979672690178
q0 = 90063199151369157959005663017593053931871580139169245885113098598755909124764417
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
mod=pow(2,266)
p0=n*inverse_mod(q0,mod)%mod
pbar=(p1<<721)+p0
PR.<x> = PolynomialRing(Zmod(n))
 
for i in range(32):
    f=pbar+x*mod*32
    f=f.monic()
    pp=f.small_roots(X=2^454,beta=0.4)
    if(pp):
        break
    pbar+=mod
 
p = pbar+pp[0]*32*mod
print(p)
#p = 159283759372043950279417056412033091802265743745598264436861098130148724970544195213191649176146680513963936883226073882981043500266750021458811522117917329282086352568217051323687992730755300271109836959298927976601834111434688928933727743853427947839181032241795612450167686056781516529650558649534989394677
  • 然后再使用Python写出解密脚本
1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
n = 18347545778876678838092757800261556931131930866012101566000425608407193858675622059415995283684230959320874387944052648148677918542763633503231962873204645415818139345588988936580526094727943067102768943117592654029397879665312089518191052154267343886226820785206334238961064175118262578895847281575656290248049404047727756356910896332939145136942219317065063060070725033146788186604738271846183709127655298440696824683099637827282095133642324657860714680107691622056420045091586609974536644773286992447027164350612852922016376888380895187804771279035652496676089183636450028327097084911908336202253562671798012457461
ct = 15659576879410368237140555530527974801613150473447768911067611094143466009251385693099110691602954207905029692682380253595062935017486879899242785756448973466690818942065250284891341066578689696180061755610538867770441139827574063212967027249650509215685566103350688284041405586915563454117672061141919712416360596137520514412607512596079964611672166435592936417138352662031529414118312166411150736015788925026636845744110093161894267707446937939130745326244186579516665160036229715964182962542836836457885170975474737620430886449029488829662146456489724775166105816909257516908496172172266375617868819982791477888289
p =159283759372043950279417056412033091802265743745598264436861098130148724970544195213191649176146680513963936883226073882981043500266750021458811522117917329282086352568217051323687992730755300271109836959298927976601834111434688928933727743853427947839181032241795612450167686056781516529650558649534989394677
q = n//p
e = 65537
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
m = pow(ct,d,n)
print(libnum.n2s(int(m)))
# BaseCTF{7074ddc3e006810688241196414e49e2}

RSA与离散对数

  • 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 bytes_to_long as b2l, long_to_bytes as l2b, getPrime
from Crypto.Cipher import AES
from random import randint


flag = b"flag{test_flag}"

pad = lambda x: x+b'\x00'*(16-len(x)%16)

def encrypt(KEY):
    cipher= AES.new(KEY,AES.MODE_ECB)
    encrypted =cipher.encrypt(flag)
    return encrypted
def decrypt(KEY):
    cipher= AES.new(KEY,AES.MODE_ECB)
    decrypted =cipher.decrypt(enc)
    return decrypted

flag = pad(flag)
x = randint(10 ** 7, 10 ** 8)
y = randint(10 ** 7, 10 ** 8)
n = getPrime(28)
z = pow(y, x, n)

enc = encrypt(pad(l2b(x)))
print(f'enc = {b2l(enc)}')
print(f'y = {y}')
print(f'n = {n}')
print(f'z = {z}')

'''
enc = 33416570913716503492297352041317858420349510954381249751537743898024527101872454706181188441210166165803904185550746
y = 82941012
n = 228338567
z = 51306718
'''
  • exp：
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
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b, getPrime
from Crypto.Cipher import AES
from random import randint
from sympy import discrete_log
from sympy.ntheory import isprime
pad = lambda x: x+b'\x00'*(16-len(x)%16)

enc = 33416570913716503492297352041317858420349510954381249751537743898024527101872454706181188441210166165803904185550746
y = 82941012
n = 228338567
z = 51306718

# 检查 n 是否为素数
if not isprime(n):
    raise ValueError("n 必须是素数")

# 计算离散对数
try:
    x = discrete_log(n, z, y)
    print(f"离散对数 x 的值是: {x}")
except Exception as e:
    print(f"无法计算离散对数: {e}")
def encrypt(KEY):
    cipher= AES.new(KEY,AES.MODE_ECB)
    encrypted =cipher.encrypt(flag)
    return encrypted
def decrypt(KEY):
    cipher = AES.new(KEY,AES.MODE_ECB)
    decrypted = cipher.decrypt(l2b(enc))
    return decrypted

flag = decrypt(pad(l2b(x)))
print(flag)
# b'BaseCTF{BF3DCONZ-67FE-ENZU-385S-CSNI13B2}\x00\x00\x00\x00\x00\x00\x00'

共模攻击

题型一e1、e2互素

题型二e1、e2不互素

  • 题目来源：BaseCTF[week3] exgcd

  • 题目附件

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'BaseCTF{}'
m=bytes_to_long(flag)

p=getPrime(1024)
q=getPrime(1024)

n=p*q
e1=3747
e2=2991

c1=pow(m,e1,n)
c2=pow(m,e2,n)

print("n =",n)
print("e1 =",e1)
print("e2 =",e2)
print("c1 =",c1)
print("c2 =",c2)

"""
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307
e1 = 3747
e2 = 2991
c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
"""

  • 解法与题型基本上相同，就是要有限域开方,开方次数为e1，e2的最大公因数

  • exp:

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

e1=3747
e2=2991
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307

c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
g, s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
m = libnum.nroot(m,3)
print(long_to_bytes(m))