openssl分解型

给两个文件,xx.pub/pem flag.enc

flag.enc不能直接打开,需要解密

openssl分解得到模数

1
2
3
4
5
6
7
8
9
10
11
12
13
[email protected]:/tools/rsatool-master# openssl rsa -pubin -text -modulus -in public.pem
RSA Public-Key: (256 bit)
Modulus:
00:ca:00:f5:ed:7b:33:b9:bd:42:1e:77:31:8a:a1:
78:e7:5d:ed:e3:cb:1b:c7:d4:7a:7d:14:3b:e7:49:
1c:90:25
Exponent: 65537 (0x10001)
Modulus=CA00F5ED7B33B9BD421E77318AA178E75DEDE3CB1BC7D47A7D143BE7491C9025
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMoA9e17M7m9Qh53MYqheOdd7ePLG8fU
en0UO+dJHJAlAgMBAAE=
-----END PUBLIC KEY-----

Modulus转为10进制

1
2
>>> int('C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD',16)
87924348264132406875276140514499937145050893665602592992418171647042491658461

Exponent就是e,下面的脚本需要用到

yafu分解或者在线网站 求出p q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
E:\tools\yafu-1.34>yafu-x64
factor(91368892744156824784111061767736072407911145707607105701466887321431798747173)
。。。。省略一部分
starting SIQS on c77: 91368892744156824784111061767736072407911145707607105701466887321431798747173

==== sieving in progress (1 thread): 36224 relations needed ====
==== Press ctrl-c to abort and save state ====
34417 rels found: 17898 full + 16519 from 180811 partial, (2016.99 rels/sec)

SIQS elapsed time = 103.7343 seconds.
Total factoring time = 120.1755 seconds


***factors found***

P39 = 290579950064240059571837821251441436997
P39 = 314436328879392457343835667929324128609

ans = 1

脚本求得私钥文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!usr/bin/env python
# coding = utf-8
import math
import sys
from Crypto.PublicKey import RSA
keypair = RSA.generate(1024)
keypair.p = 290579950064240059571837821251441436997
keypair.q = 314436328879392457343835667929324128609
keypair.e = 65537
keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))
i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1
private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

openssl解密,加密的flag.enc

1
[email protected]:/tools/rsatool-master# openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec

flag.dec文件,就是解密后的文件

1
2
[email protected]:/tools/rsatool-master# cat flag.dec 
whalectf{256_n_get}

例题2 Jarvis medium rsa

Rabin算法

典型特征e=2

以这道题为例 JarvisOJ - hardRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
[email protected]:~/桌面/JarvisOJ - hardRSA# openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
RSA Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 2 (0x2)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgEC
-----END PUBLIC KEY-----

通过openssl分解可以看到,e=2 e最不该等于的值就是2,应该使用rabin算法破解

工具

使用D001UM3师傅的工具,一把梭

1
[email protected]:/tools/CTF-RSA-tool-master# python solve.py --verbose -k pubkey.pem --decrypt flag.enc

就能拿到flag

脚本

同样先分解n

1
2
3
4
5
6
7
8
9
10
11
12
13
[email protected]:~/桌面/hardRSA# openssl rsa -pubin -text -modulus -in pubkey.pem
RSA Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 2 (0x2)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDowDQYJKoZIhvcNAQEBBQADKQAwJgIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgEC
-----END PUBLIC KEY-----

16进制转10进制

1
2
>>> int('C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD',16)
87924348264132406875276140514499937145050893665602592992418171647042491658461L

yafu分解 得到p q

1
2
P39 = 319576316814478949870590164193048041239
P39 = 275127860351348928173285174381581152299

说一下 为什么pqe都知道了 没有去计算d 因为d e不互素 没有办法求逆元

拿脚本一跑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import libnum
import gmpy2
f = open('flag.enc','r')
c = f.read()
c = libnum.s2n(c)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
r = pow(c,(p+1)/4,p)
s = pow(c,(q+1)/4,q)
a = gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
x =(a*p*s+b*q*r)%n
y =(a*p*s-b*q*r)%n
print libnum.n2s(x%n)
print libnum.n2s((-x)%n)
print libnum.n2s(y%n)
print libnum.n2s((-y)%n)

再放一个 大佬们 用python计算n e的脚本 不过这个貌似 也需要用yafu 分解得到pq

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 gmpy2
import string
from Crypto.PublicKey import RSA
with open('pubkey.pem', 'r') as f:
key = RSA.importKey(f)
N = key.n
e = key.e
with open('flag.enc', 'r') as f:
cipher = f.read().encode('hex')
cipher = string.atoi(cipher, base=16)
q = ......
p = ......
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % N
d = N - int(c)
for i in (a, b, c, d):
s = '%x' % i
if len(s) % 2 != 0:
s = '0' + s
print s.decode('hex')

共模攻击

条件

若干次加密,e不同,n相同,m相同。就可以在不分解n和求d的前提下,解出明文m

两个密文使用了同一个模数N, 在知道e1,e2,c1,c2的情况下,推算出明文m1,m2

e1 e2互素

gcd(e1,e2)=1

e1*s1 +e2*s2=1

通过扩展欧几里得算法

可以推算出 s1 s2

python 实现

gcdext(a,b) 返回一个3元素元组(g,s,t)

g=gcd(a,b) g=a*s+b*t

1
2
>>> gmpy2.gcdext(5,17)
(mpz(1), mpz(7), mpz(-2))

因为a b互质gcd=1 5*7+17*(-2)=1

推算过程

c1=m^e1%n

c2=m^e2%n

1
(c1^s1*c2^s2) = ((m^e1%n)^s1*(m^e2%n)^s2)%n
1
(c1^s1*c2^s2) = ((m^e1)^s1*(m^e2)^s2)%n

简化

1
(c1^s1*c2^s2) = (m^(e1^s1+e2^s2))%n
1
2
(c1^s1*c2^s2) = (m^(1))%n
(c1^s1*c2^s2) = m%n

偷的大佬的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/python
#coding:utf-8
#@Author:醉清风

import gmpy2
from Crypto.Util.number import long_to_bytes

e1 = 17
e2 = 65537
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
c1=int(open('./flag.enc1','rb').read().encode('hex'),16)
c2=int(open('./flag.enc2','rb').read().encode('hex'),16)


_, r, s = gmpy2.gcdext(e1, e2) #求出r s

m = pow(c1, r, n) * pow(c2, s, n) % n # (a * b) % n ≡ (a % n * b % n) % n
print long_to_bytes(m)

eg2: jarvis very hard rsa

共享素数攻击

也叫公约数分解 和共模攻击有点不同,这里的n不一样 但是使用了相同的公约数p

条件

题目给了多个n 都是2048bit 4096bit 无法正面杠

一个e 也就是私钥是确定的

这种情况下多是 多个n之间有一个相同的q或p ,可以根据多个n求出公约数p 然后利用n=pq 求出q

e 一般就按65537来

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
import gmpy2
import libnum
#求公约数
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
n1=18674375108313094928585156581138941368570022222190945461284402673204018075354069827186085851309806592398721628845336840532779579197302984987661547245423180760958022898546496524249201679543421158842103496452861932183144343315925106154322066796612415616342291023962127055311307613898583850177922930685155351380500587263611591893137588708003711296496548004793832636078992866149115453883484010146248683416979269684197112659302912316105354447631916609587360103908746719586185593386794532066034112164661723748874045470225129298518385683561122623859924435600673501186244422907402943929464694448652074412105888867178867357727

n2=20071978783607427283823783012022286910630968751671103864055982304683197064862908267206049336732205051588820325894943126769930029619538705149178241710069113634567118672515743206769333625177879492557703359178528342489585156713623530654319500738508146831223487732824835005697932704427046675392714922683584376449203594641540794557871881581407228096642417744611261557101573050163285919971711214856243031354845945564837109657494523902296444463748723639109612438012590084771865377795409000586992732971594598355272609789079147061852664472115395344504822644651957496307894998467309347038349470471900776050769578152203349128951

c1=0x8BD7BF995BF9E16A0D04ADB49A2411C74FFDB0DB4F35DB3A79A1B44691947C9824085BC4CA5F7F4EFA3C8FD0BC3E870AA6D5E15307A63A2172C44C5903D35785B8D06B51651EE7106B070D5A6AABA089AB67609661265B74914C865F863DC1D2DC08CE0B026107A74EC3FDC62666B50110B9D15A243EAAD6F53646929A3369285404868E42DD0BBE92D956018E3C0B36EF5E9516E433228CFDD06D6E662EC0A9A31061EA11F61CA17EABF43D2D4977FC9D6FC53AB6DC01509401B8D9A46B59A9ADAA97D54CC50C27445E4C21B893510620EC3566AD6E8727FA147437B207505217E6F2DF009E2286C8354D281374D7802D08A2062FE48DBF135BBCAB120EBF84
c2=0x8C3CF3161AA3E37831030985C60566A7604688B73E5B1D3B36E72EF06ED4F71289EFE80E0D94BD755034E6C210F17DA85B9D0388F3AD104C68BC514A8EB1569A109EB5F266F7C5FA4DDFA638258949B43D4CF1406720CCD4CA11E74FDF8AEB35C56A79781C87157FC4213573329C5B0FF411F8A4F34580AA103DB9FD403C0D409FA11860A7C4595FDC49DC2CF94E5112B772E5DEC8F17E24B10A7FD7A95DCB87BE5E27C32FC931574A7847BC506A61EFE9DB3D3F612143845FE80D7B3EA548B886A67A29CBDB2775B1F91178B6DA763F1A6ECFF46592E4C7FFAAB6C9FEF29D9CB9E035A3D98ECFFB26BA2EEAA56D1CD096E6A2CF9A58086CAD7718DDA5CB0C1B
e=65537
p1=gcd(n1,n2)
print "p1",p1
q1=n1/p1
q2=n2/p1
phi1=(p1-1)*(q1-1)
phi2=(p1-1)*(q2-1)
d1=gmpy2.invert(e,phi1)
d2=gmpy2.invert(e,phi2)
print "d1",d1
print "d2",d2
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
print "m1=%s"%m1
#print "flag1 is",libnum.n2s(m1)
print "flag2 is",libnum.n2s(m2)

低解密指数攻击

e过小

当e特别小时,m^e就有可能小于n 那么这时的密文c 就是m^e 直接开根号爆破

当m^e大于n时,假定使用的e=3
$$
c=m^3modN
$$

$$
m^3=c+k×N
$$

$$
m=\sqrt[3]{c+k×n}
$$

爆破k的值,

1
开方使用gmpy2.iroot函数 python实现要使用gmpy2库,利用gmpy.iroot(a,b),理解为a开b次方,这个函数的返回值为一个(x,y)元组,其中x为结果值,y为一个bool型变量,如果x为整数,y=True,否则y=False

例题 jarvis extremely hard rsa

先提取n 这里的n太大 不能分解

1
openssl rsa -pubin -text -modulus -in pubkey.pem

n转为10进制 貌似不转为10进制 直接使用16进制也可以

1
int('B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8',16)

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from libnum import s2n,n2s
from gmpy2 import iroot
n = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e = 3
f = open('flag.enc','rb')
c= f.read()
c = s2n(c)
f.close()
i = 0
while 1:
res = iroot(c+i*n,3)
if(res[1] == True):
print res[0]
break
print "i="+str(i)
i = i+1
#i=118719487
print n2s(res[0])
# 结果
# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}

e过大

wiener crack

e较大 d就较小,当
$$
d<\frac{1}{3}N^{\frac{1}{4}}
$$
就可以使用wiener crack来获取密钥

下载wiener attack

https://github.com/pablocelayes/rsa-wiener-attack

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.PublicKey import RSA
import ContinuedFractions, Arithmetic
import libnum
def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print("Hacked!")
return d
return False
n=460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597L
e=354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619L
c=38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192

d = wiener_hack(e, n)
m=pow(c,d,n)
print libnum.n2s(m)
print d

低解密指数广播攻击

题目一般是这样的

我们有多组(c,n),但是他们都是用同样的公钥加密同样的消息,且这里的公钥是一个低指数

image

中国剩余定理 一把梭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: cp936 -*-
import gmpy2
import time
def CRT(items):
N = reduce(lambda x, y: x * y, (i[1] for i in items))
result = 0
for a, n in items:
m = N / n
d, r, s = gmpy2.gcdext(n, m)
if d != 1: raise Exception("Input not pairwise co-prime")
result += a * s * m
return result % N, N
# 读入 e, n, c
e = 9
n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L]
c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L]
print '[+]Detecting m...'
data = zip(c, n)
x, n = CRT(data)
realnum = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print ' [-]m is: ' + '{:x}'.format(int(realnum)).decode('hex')
print '[!]All Done!'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
id1 = 1002
id2 = 2614
c1 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c5bb724d1cee07e221e028d9b8bc24360208840fbdfd4794733adcac45c38ad0225fde19a6a4c38e4207368f5902c871efdf1bdf4760b1a98ec1417893c8fce8389b6434c0fee73b13c284e8c9fb5c77e420a2b5b1a1c10b2a7a3545e95c1d47835c2718L
c2 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c72722fe4fe5a901e2531b3dbcb87e5aa19bbceecbf9f32eacefe81777d9bdca781b1ec8f8b68799b4aa4c6ad120506222c7f0c3e11b37dd0ce08381fabf9c14bc74929bf524645989ae2df77c8608d0512c1cc4150765ab8350843b57a2464f848d8e08L
n = 25357901189172733149625332391537064578265003249917817682864120663898336510922113258397441378239342349767317285221295832462413300376704507936359046120943334215078540903962128719706077067557948218308700143138420408053500628616299338204718213283481833513373696170774425619886049408103217179262264003765695390547355624867951379789924247597370496546249898924648274419164899831191925127182066301237673243423539604219274397539786859420866329885285232179983055763704201023213087119895321260046617760702320473069743688778438854899409292527695993045482549594428191729963645157765855337481923730481041849389812984896044723939553
a = 1
b = id1 - id2
def getmessage(a, b, c1, c2, n):
b3 = gmpy2.powmod(b, 3, n)
part1 = b * (c1 + 2 * c2 - b3) % n
part2 = a * (c1 - c2 + 2 * b3) % n
part2 = gmpy2.invert(part2, n)
return part1 * part2 % n
message = getmessage(a, b, c1, c2, n) - id2
message = hex(message)[2:]
if len(message) % 2 != 0:
message = '0' + message
print message.decode('hex')

参考链接

https://www.freebuf.com/articles/others-articles/161475.html

http://yugod.xmutsec.com/index.php/2018/03/31/28.html

https://www.tuicool.com/articles/IzuYfu

https://www.tr0y.wang/2017/11/06/CTFRSA/index.html