RSA总结

关于RSA的一些总结

最近一段时间比赛比较多，密码学的题也是各种各样的，有时候会碰到RSA，想想上学期学的数论，RSA就讲了整整一个月，最后发现代码上还是应用不了，就像没学一样，毕竟在实际生活中好多加密算法都是设计好的。为了让学过的东西不要白学，抽点时间结合题目，对RSA进行一下总结，网上好多关于RSA的文章写的都挺好的，但还是喜欢自己动手做一遍。本文没有啥原创的东西，主要是对学习的一个记录。

RSA简介：

上图是对RSA算法非对称加解密的一个描述，也是RSA算法最根本的东西，下面说一下RSA算法被攻击的可能性（有没有在知道公钥的情况下推导出私钥）

要知道的理论是：
    ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。 
    φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 
    n=pq。只有将n因数分解，才能算出p和q。
所以：如果n可以被分解，那就可以推到出d,私钥就可以被破解，但实际上p,q是大素数，分解是很困难的

一些理论支撑：

欧拉函数：φ(n)是小于等于n的数中与n互质的数的数目
欧拉函数是积性函数——若p,q互质，φ(p*q)= φ(p) *φ(q) 
若p为质数，则φ(p)=p-1

同余定理：给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。 
性质： 
1 自反性 a≡a (mod m) 
2 对称性 若a≡b(mod m)，则b≡a (mod m) 
3 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m) 
4 同余式相加 若a≡b (mod m)，c≡d(mod m)，则a+-c≡b+-d (mod m) 
5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)

求逆元：指有一个整数d，可以使得e*d被φ(n)除的余数为1，即e*d ≡ 1 (mod φ(n))，这个式子等于e*d - 1 = k*φ(n)

一些程序代码上的支撑：（都是用python实现算法的应用）

快速幂取模：等价于pow方法

def mod(c,d,n):#等价于自带的pow(c,d,n)
    r=1
    while d>0:
        c=c%n
        if d&1:
            r=(r*c)%n
        d>>=1
        c=(c*c)%n
    return r

模逆运算（就是求逆元，主要基于扩展欧几里得算法）

python实现代码如下：

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得逆元

出来通过自己编写实现之外还可以通过gmpy2和libnum这两个库函数实现：

#coding:utf-8
from  libnum import invmod
import gmpy2
print invmod(47,30)
print gmpy2.invert(47,30)

欧几里得算法：就是求最大公约数，gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a有递归实现和迭代实现两种：

# 递归版
def gcd(a, b):
    return a if not b else gcd(b, a % b)

# 迭代版
def gcd2(a, b):
    while b:
        a, b = b, a % b
    return a

扩展欧几里得算法：本质上就是将欧几里得算法求最大公约数的过程最后转化为线性表达式：

# 递归版
def ext_euclid ( a , b ):
    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):
    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 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) #(解,最小公倍数)

应用中一些函数、模块的支撑

这里不得不感慨python的强大与方便，提供了gmpy2库、libnum库、pycrypto模块等第三方库，避免了从底层一步一步的写代码（其实也是太菜了，这种基于数论的代码是真的写不出来）

gmpy2库、libnum库，主要提供各种数学运算的函数库，向求逆元，取模等运算直接调运函数就可以，很便捷
关于两个库的说明链接如下：

pycrypto模块是python中来处理加密解密等信息安全相关的一个重要模块，提供了对称加密、非对称加密、散列哈希的一些计算方法，满足我们在密码学应用上的使用，就RSA可以实现公私钥的提取，生成，利用公私钥进行加解密等，之前写过的一篇文章有介绍

关于RSA中n的分解：

有在线分解：[]:http://factordb.com/

离线的[yafu]:https://sourceforge.net/projects/yafu/ （p,q相差较大或较小时可快速分解）
除了用代码，还可以用OpenSSL对一些标准格式的RSA加解密

使用OpenSSL提取公钥信息：openssl rsa -pubin -in (文件名) -text

使用OpenSSL提取私钥信息：openssl rsa -in (文件名) -text

使用OpenSSL进行公钥加密：openssl rsautl -encrypt -in test -out test.enc -inkey asn1pub.pem -pubin

使用OpenSSL进行私钥解密：openssl rsautl -decrypt -in test.enc -out test.dec -inkey asn1enc.pem

使用OpenSSL进行私钥签名：openssl rsautl -sign -in test -out test.sig-inkey asn1enc.pem

使用OpenSSL进行公钥验证：openssl rsautl -verify -in test.sig -out test.vfy -inkey asn1pub.pem -pubin

一些实际的应用：

RSA直接解密：

若已知私钥d，则可以直接解密： m=pow(c,d,n) :

p:0x9a724c6747de9eadccd33f4d60ada91754b8be8c65590cafe66f69a2f4afbfd359e47ca6fd2dbde8948062dc116bc574f4313ab99b2bb6d8ae47beaa0c1ebeddL

q:0x8c1c81cc005ce3dd6d684ebb88151dc0c53b1cef8a29b1cb8121860fb57d93117bf449aac4300dc6103ac6211c6f8ae68987d99aff0dd8967a4afa00f2116873L

e:0x190a000845e9c8c2059242835432326369aaf8c7ca85e685bba968b386155a91f1f7ca1019ff23d119222e1f0dfdeb0915d2e97601ef94bf15ca6d9211e984e9038f263f4984355c397ed22d67c26da6d31acfc4d599c70cba80859bee099e5a2dc3ab23aecf58f73f44d07318f70985c623d9612efefb15bf8dab77d5d54e85L

d:0x28b95b7e3159a851cbf537e007ae49864b7dbb93fc370a5L 

c:0x23091e42fa7609c73f1941b320fad6d2ff6e47be588d1623f970f1fee7abd221c9834b208f3c888902fe87ca76ec1e1363757d93c6e25c49f1c61c72b141c0b8848b54a117427d8e30eeab89694eb5f849cafecb0e5361b9b2b0e3f89e0fdbcc66a6aad4a1a4a85d828083a01a5d569b7eeb6f9151794453382b524aa52993f9L


c=0x23091e42fa7609c73f1941b320fad6d2ff6e47be588d1623f970f1fee7abd221c9834b208f3c888902fe87ca76ec1e1363757d93c6e25c49f1c61c72b141c0b8848b54a117427d8e30eeab89694eb5f849cafecb0e5361b9b2b0e3f89e0fdbcc66a6aad4a1a4a85d828083a01a5d569b7eeb6f9151794453382b524aa52993f9
d=0x28b95b7e3159a851cbf537e007ae49864b7dbb93fc370a5
n=0x9a724c6747de9eadccd33f4d60ada91754b8be8c65590cafe66f69a2f4afbfd359e47ca6fd2dbde8948062dc116bc574f4313ab99b2bb6d8ae47beaa0c1ebedd * 0x8c1c81cc005ce3dd6d684ebb88151dc0c53b1cef8a29b1cb8121860fb57d93117bf449aac4300dc6103ac6211c6f8ae68987d99aff0dd8967a4afa00f2116873

m=pow(c,d,n)
print hex(m)[2:len(hex(m))-1].decode('hex')

若已知质数p和q，则通过依次计算欧拉函数、私钥d可解密。实现如下：

def rsa_decrypt(e, c, p, q):
    phi = (p - 1) * (q - 1)
    n = p * q
    try:
        d = gmpy2.invert(e, phi) 	#求e模phi的逆
        return pow(c, d, n)
    except Exception as e:
        print "e and phi are not coprime!"
        raise e

在选取加密指数e时要求phi，e互质，也就是gcd(phi,e)==1 ，如果不满足是无法直接解密的

x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259
tell me the smallest answer of x
n = 3436415358139016629092568198745009225773259=3881 · 885445853681787330351086884500131209939
e = 33
c = 1926041757553905692219721422025224638913707
phi=(p-1)*(q-1)
gcd(phi,33)==3 -> e = 11
n分解以后不满足互素的要求，先用逆元11得到x^3的值,然后爆破X

import gmpy2
import libnum

c = 1926041757553905692219721422025224638913707
n = 3436415358139016629092568198745009225773259
e = 33
p = 3881
q = 885445853681787330351086884500131209939
phi = (p-1)*(q-1)
d = libnum.invmod(e/3, phi)
print d
x3 = pow(c, d, n)
print x3

def calc(i):
    x, b = gmpy2.iroot(x3 + i *n, 3)
    if b == 1:
        print x
        exit()
for j in xrange(0,100000000):
    calc(j)

模不互质（gcd(N1,N2)!=1）适用情况：存在两个或更多模数，且gcd(N1,N2)!=1 多个模数n共用质数，则可以很容易利用欧几里得算法求得他们的质因数之一gcd(N1,N2) ，然后这个最大公约数可用于分解模数分别得到对应的p和q，即可进行解密。

共模攻击：适用情况：明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1 对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击。

python实现的证明代码：

def common_modulus(n, e1, e2, c1, c2):
    """
    ref: https://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack
    ∵gcd(e1,e2)==1,∴由扩展欧几里得算法，存在e1*s1+e2*s2==1
    ∴m==m^1==m^(e1*s1+e2*s2)==((m^e1)^s1)*((m^e2)^s2)==(c1^s1)*(c2^s2)
    """
    assert (libnum.gcd(e1, e2) == 1)
    _, s1, s2 = gmpy2.gcdext(e1, e2)
    # 若s1<0，则c1^s1==(c1^-1)^(-s1)，其中c1^-1为c1模n的逆元。
    m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
    m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
    return m % n

Xman-RSA(这道题利用了共模攻击和模不互素)

from gmpy2 import is_prime
from os import urandom
import base64


def bytes_to_num(b):
    return int(b.encode('hex'), 16)


def num_to_bytes(n):
    b = hex(n)[2:-1]
    b = '0' + b if len(b) % 2 == 1 else b
    return b.decode('hex')


def get_a_prime(l):
    random_seed = urandom(l)

    num = bytes_to_num(random_seed)

    while True:
        if is_prime(num):
            break
        num += 1
    return num


def encrypt(s, e, n):
    p = bytes_to_num(s)
    p = pow(p, e, n)
    return num_to_bytes(p).encode('hex')


def separate(n):
    p = n % 4
    t = (p * p) % 4
    return t == 1


f = open('flag.txt', 'r')
flag = f.read()

msg1 = ""
msg2 = ""
for i in range(len(flag)):
    if separate(i):
        msg2 += flag[i]
    else:
        msg1 += flag[i]

p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1 * p2
n2 = p1 * p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)

e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4 * p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)

print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))

n2，n3已知，利用共模攻击得到n1，由gcd(n1,n2)==p1 分解n1，n2得到flag：

# -*- coding: utf-8 -*-
# by https://findneo.github.io/

import base64
import libnum
import gmpy2


def fix_py():
    # decode encryption.encrypted
    s1 = 'abdefghijklmpqrtuvwxyz'
    s2 = 'dmenwfoxgpyhirasbktclu'
    f1 = open('encryption.encrypted')
    with open('encryption.py', 'w') as f2:
        for i in f1.readlines():
            tmp = ''
            for j in i:
                tmp += s2[s1.index(j)] if j in s1 else j
            f2.write(tmp)
# fix_py()
def common_modulus(n, e1, e2, c1, c2):
    assert (libnum.gcd(e1, e2) == 1)
    _, s1, s2 = gmpy2.gcdext(e1, e2)
    m = pow(c1, s1, n) if s1 > 0 else pow(gmpy2.invert(c1, n), -s1, n)
    m *= pow(c2, s2, n) if s2 > 0 else pow(gmpy2.invert(c2, n), -s2, n)
    m %= n
    return m


[n2, n3] = map(lambda x: int(base64.b64decode(x).encode('hex'), 16),
               open('n2&n3').readlines())
[n1c1, n1c2] = map(lambda x: int(x, 16), open('n1.encrypted').readlines())
[msg1c1, msg2c2] = map(lambda x: int(x, 16), open('ciphertext').readlines())
# 通过共模攻击得到n1
e1 = 0x1001
e2 = 0x101
n1 = common_modulus(n3, e1, e2, n1c1, n1c2)
# n1,n2有一个共有质因数p1
# n1 += n3  # 存在n3比n1小的可能，并且确实如此;貌似主办方中途改题，把n1改成小于n3了。
p1 = gmpy2.gcd(n1, n2)
assert (p1 != 1)
p2 = n1 / p1
p3 = n2 / p1
e = 0x1001
d1 = gmpy2.invert(e, (p1 - 1) * (p2 - 1))
d2 = gmpy2.invert(e, (p1 - 1) * (p3 - 1))
msg1 = pow(msg1c1, d1, n1)
msg2 = pow(msg2c2, d2, n2)
msg1 = hex(msg1)[2:].decode('hex')
msg2 = hex(msg2)[2:].decode('hex')
print msg1, msg2
# XA{RP0I_0Itrsigi s.y
# MNCYT_55_neetnvmrap}
# XMAN{CRYPT0_I5_50_Interestingvim rsa.py}

RSA-CRYPTO(有两个公钥文件和两个flag文件。提取公钥对比，n相同且可解密，共模攻击)

from Crypto.PublicKey import RSA

with open('./pubkey2.pem', 'r') as f:
     key = RSA.importKey(f)
     n = key.n
     e = key.e

print (n)
print (e)
#提取两个公钥都是这个脚本

#coding:utf-8
import gmpy2
import string
from Crypto.Util.number import long_to_bytes
from base64 import *

#共模攻击
n =  0x8989a398988456b3fef4a6ad86df3c99577f8978048de5436befc30d8d8c94958912aa526ff333b66857306ebb8de36c2c396a84efdc5d382502daa1a3f3b6e97502d2e31c849330f5b4c95257a149a97f5954eaf89341147adcdd4e950fff74e30bbe622876b42eeac86df4ad9715d05b5604aa8179424c7d9ac46bd6b5f322b2b5728ba148704a25a8efcc1e7c84ea7e5ce3e01703f04f94a431d9954bd7ae2c7dd6e879b35f8a2d4a5efbe737257bf99bd9ee66b15aff233fc77b558a487da5952fbe2b923da9c5eb46788c050336b7e36a5ed82d5c1b2aeb0e45bee405cbe72481db2568aa829eeac87d201a5a8ff5ee6f0be38192ab2839635f6c664217L
e1 = 2333
e2 = 23333

with open('./flag1.enc','r') as f:
    cipher1 =  f.read()
    cipher1 = b64decode(cipher1).encode('hex')
    cipher1 = string.atoi(cipher1,base = 16)

with open('./flag2.enc','r') as f:
    cipher2 = f.read()
    cipher2 = b64decode(cipher2).encode('hex')
    cipher2 = string.atoi(cipher2,base = 16)  #将字符串转为整型数字,base 指定进制

gcd, s, t = gmpy2.gcdext(e1, e2)        #返回一个三元素的元组 g == gcd（a，b）和g == a * s + b * t

if s < 0:
    s = -s
    cipher1 = gmpy2.invert(cipher1,n)   #求cipher1模n的逆(求逆元)

if t < 0:
    t = -t
    cipher2 = gmpy2.invert(cipher2,n)

#powmod（x，y，m）返回（x ** y）mod m。指数y可以是负数，如果x mod m的逆存在，则返回正确的结果。否则，引发ValueError
plain = gmpy2.powmod(cipher1, s, n) * gmpy2.powmod(cipher2, t, n) % n

print long_to_bytes(plain)

小明文攻击：适用情况：e较小，一般为3。公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0，爆破k或直接开三次方即可。

Jarvis OJ Extremely hard RSA

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

Rabin加密中的N可被分解:Rabin加密是RSA的衍生算法，e==2是Rabin加密典型特征,一般先通过其他方法分解得到p，q，然后解密.

python实现：

def rabin_decrypt(c, p, q, e=2):
    n = p * q
    mp = pow(c, (p + 1) / 4, p)
    mq = pow(c, (q + 1) / 4, q)
    yp = gmpy2.invert(p, q)
    yq = gmpy2.invert(q, p)
    r = (yp * p * mq + yq * q * mp) % n
    rr = n - r
    s = (yp * p * mq - yq * q * mp) % n
    ss = n - s
    return (r, rr, s, ss)

Jarvis OJ hard RSA

import gmpy2
import libnum
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=2
c=int(open('hardRSA.rar/flag.enc','rb').read().encode('hex'),16)
mp=pow(c,(p+1)/4,p)
mq=pow(c,(q+1)/4,q)
yp=gmpy2.invert(p,q)
yq=gmpy2.invert(q,p)
r=(yp*p*mq+yq*q*mp)%n
rr=n-r
s=(yp*p*mq-yq*q*mp)%n
ss=n-s
print libnum.n2s(r)
print libnum.n2s(rr)
print libnum.n2s(s)
print libnum.n2s(ss)

Wiener’s Attack:适用情况：e过大或过小(低解密指数攻击)

工具地址：[]:https://github.com/pablocelayes/rsa-wiener-attack

这里脚本运行报错的话，再脚本前加上：

1 2	import sys sys.setrecursionlimit(10000000)

python实现：

from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic

def wiener_hack(e, n):
    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

nextrsa-Level2

n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1L
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46fL
d = wiener_hack(e, n)
print d

私钥文件修复:适用情况：提供破损的私钥文件

Jarvis OJ-God Like RSA []:https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html
LSB Oracle Attack:适用情况：可以选择密文并泄露最低位

在一次RSA加密中，明文为m，模数为n，加密指数为e，密文为c。我们可以构造出c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n ，因为m的两倍可能大于n，所以经过解密得到的明文是 m'=(2*m)%n 。我们还能够知道 m' 的最低位lsb 是1还是0。因为n是奇数，而2*m 是偶数，所以如果lsb是0，说明(2*m)%n 是偶数，没有超过n，即m<n/2.0 ，反之则m>n/2.0 。举个例子就能明白2%3=2 是偶数，而4%3=1 是奇数。以此类推，构造密文c"=(4^e)*c)%n 使其解密后为m"=(4*m)%n ，判断m" 的奇偶性可以知道m 和 n/4 的大小关系。所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间

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)

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

选择密文攻击:适用情况：可以构造任意密文并获得对应明文(在一个RSA加密过程中，明文为m，密文为c，模数为n，加密指数为e，选取x以满足gcd(x,n)==1 从而使x模n的逆存在，构造密文 c'=c*(x^e) 使解密后明文为 m'=(m*x)%n ，则m=m'*x^-1(mod n))

广播攻击:适用情况：模数n、密文c不同，明文m、加密指数e相同。一般会是e=k，然后给k组数据(使用不同的模数n，相同的公钥指数e加密相同的信息。就会得到多个(m^e) ==ci (mod ni)，将(m^e)视为一个整体M，这就是典型的中国剩余定理适用情况)

nextrsa-Level9

m = random.randint(0x100000000000, 0xffffffffffff)
e = 3
n1 = 0x43d819a4caf16806e1c540fd7c0e51a96a6dfdbe68735a5fd99a468825e5ee55c4087106f7d1f91e10d50df1f2082f0f32bb82f398134b0b8758353bdabc5ba2817f4e6e0786e176686b2e75a7c47d073f346d6adb2684a9d28b658dddc75b3c5d10a22a3e85c6c12549d0ce7577e79a068405d3904f3f6b9cc408c4cd8595bf67fe672474e0b94dc99072caaa4f866fc6c3feddc74f10d6a0fb31864f52adef71649684f1a72c910ec5ca7909cc10aef85d43a57ec91f096a2d4794299e967fcd5add6e9cfb5baf7751387e24b93dbc1f37315ce573dc063ecddd4ae6fb9127307cfc80a037e7ff5c40a5f7590c8b2f5bd06dd392fbc51e5d059cffbcb85555L
n2 = 0x60d175fdb0a96eca160fb0cbf8bad1a14dd680d353a7b3bc77e620437da70fd9153f7609efde652b825c4ae7f25decf14a3c8240ea8c5892003f1430cc88b0ded9dae12ebffc6b23632ac530ac4ae23fbffb7cfe431ff3d802f5a54ab76257a86aeec1cf47d482fec970fc27c5b376fbf2cf993270bba9b78174395de3346d4e221d1eafdb8eecc8edb953d1ccaa5fc250aed83b3a458f9e9d947c4b01a6e72ce4fee37e77faaf5597d780ad5f0a7623edb08ce76264f72c3ff17afc932f5812b10692bcc941a18b6f3904ca31d038baf3fc1968d1cc0588a656d0c53cd5c89cedba8a5230956af2170554d27f524c2027adce84fd4d0e018dc88ca4d5d26867L
n3 = 0x280f992dd63fcabdcb739f52c5ed1887e720cbfe73153adf5405819396b28cb54423d196600cce76c8554cd963281fc4b153e3b257e96d091e5d99567dd1fa9ace52511ace4da407f5269e71b1b13822316d751e788dc935d63916075530d7fb89cbec9b02c01aef19c39b4ecaa1f7fe2faf990aa938eb89730eda30558e669da5459ed96f1463a983443187359c07fba8e97024452087b410c9ac1e39ed1c74f380fd29ebdd28618d60c36e6973fc87c066cae05e9e270b5ac25ea5ca0bac5948de0263d8cc89d91c4b574202e71811d0ddf1ed23c1bc35f3a042aac6a0bdf32d37dede3536f70c257aafb4cfbe3370cd7b4187c023c35671de3888a1ed1303L
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print m == gmpy2.iroot(CRT([n1, n2, n3], [c1, c2, c3]), e)[0]