def egcd ( a , b ):
if (b == 0):
return 1, 0, a
else:
x , y , q = egcd( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
x , y = y, ( x - (a // b) * y )
return x, y, q
def mod_inv(a,b):
return egcd(a,b)[0]%b #求a模b得逆元
(a + b) % n ≡ (a % n + b % n) % n
(a - b) % n ≡ (a % n - b % n) % n
(a * b) % n ≡ (a % n * b % n) % n
(a ^ b) % n ≡ ((a % n) ^ b) % n //幂运算
若 a ≡ b(mod n) ,则
1.对于任意正整数c,有a^c ≡ b^c(mod n)
2.对于任意整数c,有ac ≡ bc(mod n),a+c ≡ b+c(mod n),
3.若 c ≡ d(mod n),则a-c ≡ b-d(mod n),a+c ≡ b+d(mod n),ac ≡ bd(mod n)
如果ac≡bc (mod m),且c和m互质,则a≡b (mod m)。
[理解:当且仅当c和m互质,c^-1存在,等式左右可同乘模逆。]
除法规则:
在模n意义下,a/b不再仅仅代表这两个数相除,而是指 a+k1*n 和 b+k2*n这两个组数中任意两个相除,使商为整数
因此也就可以理解,除以一个数等价于乘以它的逆
a/b ≡ c(mod n) <=> a ≡ c*(b^-1) (mod n),其中b模n的逆记作b的负一次方。
费马小定理:
a是整数,p是质数,则a^p==a(mod p),如果a不是p的倍数,还有a^(p-1) ≡ 1(mod p)
# 递归版
def ext_euclid ( a , b ):
# ref:https://zh.wikipedia.org/wiki/扩展欧几里得算法
if (b == 0):
return 1, 0, a
else:
x1 , y1 , q = ext_euclid( b , a % b ) # q = GCD(a, b) = GCD(b, a%b)
x , y = y1, ( x1 - (a // b) * y1 )
return x, y, q
# 迭代版
def egcd(a, b):
# ref:https://blog.csdn.net/wyf12138/article/details/60476773
if b == 0:
return (1, 0, a)
x, y = 0, 1
s1, s2 = 1, 0
r, q = a % b, a / b
while r:
m, n = x, y
x = s1 - x * q
y = s2 - y * q
s1, s2 = m, n
a, b = b, r
r, q = a % b, a / b
return (x, y, b)
def CRT(mi, ai):
# mi,ai分别表示模数和取模后的值,都为列表结构
# Chinese Remainder Theorem
# lcm=lambda x , y:x*y/gcd(x,y)
# mul=lambda x , y:x*y
# assert(reduce(mul,mi)==reduce(lcm,mi))
# 以上可用于保证mi两两互质
assert (isinstance(mi, list) and isinstance(ai, list))
M = reduce(lambda x, y: x * y, mi)
ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
return reduce(lambda x, y: x + y, ai_ti_Mi) % M
def GCRT(mi, ai):
# mi,ai分别表示模数和取模后的值,都为列表结构
assert (isinstance(mi, list) and isinstance(ai, list))
curm, cura = mi[0], ai[0]
for (m, a) in zip(mi[1:], ai[1:]):
d = gmpy2.gcd(curm, m)
c = a - cura
assert (c % d == 0) #不成立则不存在解
K = c / d * gmpy2.invert(curm / d, m / d)
cura += curm * K
curm = curm * m / d
cura %= curm
return (cura % curm, curm) #(解,最小公倍数)
for i in range(1000000):
# 推荐使用gmpy2库运算,用pow开立方不可行
if gmpy2.iroot(m + i * n, 3)[1]:
x = gmpy2.iroot(m + i * n, 3)[0]
# i==243277,x==9420391510958023
break
def small_msg(e, n, c):
print time.asctime(), "Let's waiting..."
for k in xrange(200000000):
if gmpy2.iroot(c + n * k, e)[1] == 1:
print time.asctime(), "...done!"
return gmpy2.iroot(c + n * k, 3)[0]
例子:Extremely hard RSA
题目提供的n是4096位的,e=3。
import gmpy2,binascii,libnum,time
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e=3
res=0
c=int(open('extremelyhardRSA.rar/flag.enc','rb').read().encode('hex'),16)
print time.asctime()
for i in xrange(200000000):
if gmpy2.iroot(c+n*i,3)[1]==1:
res=gmpy2.iroot(c+n*i,3)[0]
print i,res
print libnum.n2s(res)
print time.asctime()
break
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
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
例子:2018强网杯nextrsa-Level2
n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1L
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46fL
d = wiener_hack(e, n)
print d #42043
import decimal
def oracle():
return lsb == 'odd'
def partial(c, e, n):
k = n.bit_length()
decimal.getcontext().prec = k # for 'precise enough' floats
lo = decimal.Decimal(0)
hi = decimal.Decimal(n)
for i in range(k):
if not oracle(c):
hi = (lo + hi) / 2
else:
lo = (lo + hi) / 2
c = (c * pow(2, e, n)) % n
# print i, int(hi - lo)
return int(hi)
例子:QCTF2018-XMan选拔赛/Baby RSA
题目如下
e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
λ nc 47.96.239.28 23333
----------------------------- baby rsa -----------------------------
Come and Decode your data
If you give me ciphertext, I can tell you whether decoded data is even or odd
You can input ciphertext(hexdecimal) now
1
odd
解题脚本:
# -*- coding: utf-8 -*-
# by https://findneo.github.io/
# ref:
# https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack
# https://ctf.rip/sharif-ctf-2016-lsb-oracle-crypto-challenge/
# https://introspelliam.github.io/2018/03/27/crypto/RSA-Least-Significant-Bit-Oracle-Attack/
import libnum, gmpy2, socket, time, decimal
def oracle(c1):
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
hostname = '47.96.239.28'
port = 23333
s.connect((hostname, port))
s.recv(1024)
s.send(hex(c1)[2:].strip("lL") + '\n')
res = s.recv(1024).strip()
s.close()
if res == 'even': return 0
if res == 'odd':
return 1
else:
assert (0)
def partial(c, n):
global c_of_2
k = n.bit_length()
decimal.getcontext().prec = k # allows for 'precise enough' floats
lower = decimal.Decimal(0)
upper = decimal.Decimal(n)
for i in range(k):
possible_plaintext = (lower + upper) / 2
# lower==0 when i<1809
flag = oracle(c)
if not flag:
upper = possible_plaintext # plaintext is in the lower half
else:
lower = possible_plaintext # plaintext is in the upper half
c = (c * c_of_2) % n # multiply y by the encryption of 2 again
print i, flag, int(upper - lower)
# time.sleep(0.2)
# By now, our plaintext is revealed!
return int(upper)
def main():
print "[*] Conducting Oracle attack..."
return partial((c * c_of_2) % n, n)
if __name__ == '__main__':
e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
c_of_2 = pow(2, e, n)
m = main()
# m = 560856645743734814774953158390773525781916094468093308691660509501812349
print libnum.n2s(m)
# QCTF{RSA_parity_oracle_is_fun}