RSA 介绍

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。

基本原理

公钥与私钥的产生

随机选择两个不同大质数 $p$ 和 $q$，计算 $N = p \times q$
根据欧拉函数，求得 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$
选择一个小于 $\varphi (N)$ 的整数 $e$，使 $e$ 和 $\varphi (N)$ 互质。并求得 $e$ 关于 $\varphi (N)$ 的模反元素，命名为 $d$，有 $ed\equiv 1 \pmod {\varphi (N)}$
将 $p<200b>$ 和 $q<200b>$ 的记录销毁

此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。

公钥/私钥文件读取

from Crypto.PublicKey import RSA
pk=b'''-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA0StjnfdZqZya21dQC71j
UEGqcPjnP26hWLI7mvV1kVz2jPjlewRbvrz3ipvKcr8OY8tuw1PWYUIEjLaetfIM
3GuvbIXnfm8qqQbcWGj8sPAzDetVB27fGyJu9Ukm3SrTyUPI6zXLjIWEjgXqhoCY
ihgnAbag3FSWd2DKwoE2rVs9nxz3lSuJjPqvhjqQv9WN8Po/NYp+uLy+G/zxOHK7
ufzCszCjjz/WiUZ/7yLwJ1SfU9Rg6f67SPGuFfe/upMGlkH9U8RvyXFWD1lV2Pbk
GfWYGpujk3GNeF9YZZYH9RH2zEB3g04FnzaOsFvKeWTqLcjNGxP2KinqJEo4dv9Z
ZwIDAQAB
-----END PUBLIC KEY-----'''
keyPub = RSA.importKey(pk)

>>> keyPub
RsaKey(n=26405201714915839490865227813246218372938736243516916108608439705738170543023112509150522274284238701776297205717958250714972924576706985074311737321016048409831557758205687745692399643151467933196930799657476449865271038382866908177517793954543176769652784274788769353482450910551831498252972857285424471782215525406445071432588374802623485148684255853068532820859835479998199886719945699488858505070686919320144576280217196858823521754407597888769668827432569034617434944912323704501156532854074083408527717809315663187405585840074689387865750105223058720511199252150772925124516509254841404742306560035497627834727, e=65537)

$ openssl rsa -inform PEM -pubin -in pubkey.pem -text -noout
RSA Public-Key: (2048 bit)
Modulus:
    00:d1:2b:63:9d:f7:59:a9:9c:9a:db:57:50:0b:bd:
    63:50:41:aa:70:f8:e7:3f:6e:a1:58:b2:3b:9a:f5:
    75:91:5c:f6:8c:f8:e5:7b:04:5b:be:bc:f7:8a:9b:
    ca:72:bf:0e:63:cb:6e:c3:53:d6:61:42:04:8c:b6:
    9e:b5:f2:0c:dc:6b:af:6c:85:e7:7e:6f:2a:a9:06:
    dc:58:68:fc:b0:f0:33:0d:eb:55:07:6e:df:1b:22:
    6e:f5:49:26:dd:2a:d3:c9:43:c8:eb:35:cb:8c:85:
    84:8e:05:ea:86:80:98:8a:18:27:01:b6:a0:dc:54:
    96:77:60:ca:c2:81:36:ad:5b:3d:9f:1c:f7:95:2b:
    89:8c:fa:af:86:3a:90:bf:d5:8d:f0:fa:3f:35:8a:
    7e:b8:bc:be:1b:fc:f1:38:72:bb:b9:fc:c2:b3:30:
    a3:8f:3f:d6:89:46:7f:ef:22:f0:27:54:9f:53:d4:
    60:e9:fe:bb:48:f1:ae:15:f7:bf:ba:93:06:96:41:
    fd:53:c4:6f:c9:71:56:0f:59:55:d8:f6:e4:19:f5:
    98:1a:9b:a3:93:71:8d:78:5f:58:65:96:07:f5:11:
    f6:cc:40:77:83:4e:05:9f:36:8e:b0:5b:ca:79:64:
    ea:2d:c8:cd:1b:13:f6:2a:29:ea:24:4a:38:76:ff:
    59:67
Exponent: 65537 (0x10001)

$ openssl rsa -inform PEM  -in privatekey.pem -text -noout
RSA Private-Key: (2048 bit, 2 primes)
modulus:
    00:d1:2b:63:9d:f7:59:a9:9c:9a:db:57:50:0b:bd:
    63:50:41:aa:70:f8:e7:3f:6e:a1:58:b2:3b:9a:f5:
    75:91:5c:f6:8c:f8:e5:7b:04:5b:be:bc:f7:8a:9b:
    ca:72:bf:0e:63:cb:6e:c3:53:d6:61:42:04:8c:b6:
    9e:b5:f2:0c:dc:6b:af:6c:85:e7:7e:6f:2a:a9:06:
    dc:58:68:fc:b0:f0:33:0d:eb:55:07:6e:df:1b:22:
    6e:f5:49:26:dd:2a:d3:c9:43:c8:eb:35:cb:8c:85:
    84:8e:05:ea:86:80:98:8a:18:27:01:b6:a0:dc:54:
    96:77:60:ca:c2:81:36:ad:5b:3d:9f:1c:f7:95:2b:
    89:8c:fa:af:86:3a:90:bf:d5:8d:f0:fa:3f:35:8a:
    7e:b8:bc:be:1b:fc:f1:38:72:bb:b9:fc:c2:b3:30:
    a3:8f:3f:d6:89:46:7f:ef:22:f0:27:54:9f:53:d4:
    60:e9:fe:bb:48:f1:ae:15:f7:bf:ba:93:06:96:41:
    fd:53:c4:6f:c9:71:56:0f:59:55:d8:f6:e4:19:f5:
    98:1a:9b:a3:93:71:8d:78:5f:58:65:96:07:f5:11:
    f6:cc:40:77:83:4e:05:9f:36:8e:b0:5b:ca:79:64:
    ea:2d:c8:cd:1b:13:f6:2a:29:ea:24:4a:38:76:ff:
    59:67
publicExponent: 65537 (0x10001)
privateExponent: 0
prime1: 0
prime2:
    00:ee:4e:18:98:45:cc:78:ef:ef:4a:c3:e8:1d:8a:
    ef:99:7f:73:5d:58:33:b5:c7:e8:49:4b:91:74:ae:
    21:1b:a8:82:31:e2:56:7e:e6:df:99:01:32:8e:0c:
    6d:bc:5e:24:b3:43:77:47:85:ae:7e:88:ec:40:9c:
    a1:d7:29:01:e3:2a:58:2f:29:12:60:eb:98:51:fc:
    bb:0f:ff:20:80:5d:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00
exponent1: 0
exponent2: 0
coefficient: 0

from sage.all import *

n=0xd12b639df759a99c9adb57500bbd635041aa70f8e73f6ea158b23b9af575915cf68cf8e57b045bbebcf78a9bca72bf0e63cb6ec353d66142048cb69eb5f20cdc6baf6c85e77e6f2aa906dc5868fcb0f0330deb55076edf1b226ef54926dd2ad3c943c8eb35cb8c85848e05ea8680988a182701b6a0dc54967760cac28136ad5b3d9f1cf7952b898cfaaf863a90bfd58df0fa3f358a7eb8bcbe1bfcf13872bbb9fcc2b330a38f3fd689467fef22f027549f53d460e9febb48f1ae15f7bfba93069641fd53c46fc971560f5955d8f6e419f5981a9ba393718d785f58659607f511f6cc4077834e059f368eb05bca7964ea2dc8cd1b13f62a29ea244a3876ff5967
p4=0xee4e189845cc78efef4ac3e81d8aef997f735d5833b5c7e8494b9174ae211ba88231e2567ee6df9901328e0c6dbc5e24b343774785ae7e88ec409ca1d72901e32a582f291260eb9851fcbb0fff20805d            #已知P的高位
e=0x10001
pbits=1024          #P原本的位数

kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:        
    p = p4+int(roots[0]) 
    print("n: "+str(n))
    print("p: "+str(p))
    print("q: "+str(n//p))

消息加密

首先需要将消息以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

$$ m^{e}\equiv c\pmod N $$

消息解密

利用密钥 $d<200b>$ 进行解密。

$$ c^{d}\equiv m\pmod N $$

gmpy gmpy2 pycrypto

gmpy.root(a, b)`，返回一个元组 `(x, y)`，其中 `x` 为 `a` 开 `b` 次方的值，`y` 是判断 `x` 是否为整数的布尔型变量

gmpy2.iroot(a, b)，类似于 gmpy.root(a,b)

import gmpy2 as gp
import binascii
p =  
q =  
e =  
c =  
n = p*q
phi = (p-1)*(q-1)
d = gp.invert(e,phi)
m = pow(c,d,n)
print(m)
print(bytes.fromhex(hex(m)[2:]))

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

msg = 'crypto here'
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
key = PKCS1_v1_5.new(privatekey)
msg = key.decrypt(enc.decode('base64'), e)

例１　Rabin 算法

Rabin 算法的特征在于 $e=2$。

二次剩余

密文：

$$ c = m^2\bmod n $$

如果 p ≡ q ≡ 3 ( mod 4 )

import gmpy2

# 如果  p ≡ q ≡ 3 ( mod 4 )

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)

c = 
p = 
q = 
m = rabin_decrypt(c,p,q)
for i in range(4):
    try:
        print(bytes.fromhex(hex(m[i])[2:]))
    except:
        pass

如果 p ≡ 1 or q ≡ 1 ( mod 4 )

AMM, 全称为Adleman-Mander-Miller Method。在1977年他们发表的论文里只涉及了开平方根的方法，开n次方根并没有很详细的介绍。《Adleman-Manders-Miller Root Extraction Method Revisited》里三位中国人补充了他们开n次方根的方法。

from Crypto.Util.number import long_to_bytes
import random
import time
import gmpy2

# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r^(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp


c = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 4919

cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)


def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    tmp = long_to_bytes(m)
    if tmp.startswith(b'*CTF'):
        print(tmp)
        return True
    else:
        return False


# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
            exit()
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))

例2 Wiener's Attack

维纳攻击

在 d 比较小（e很大)时，攻击者可以使用 Wiener's Attack 来获得私钥。

from Crypto.Util.number import long_to_bytes

N = 13123058934861171416713230498081453101147538789122070079961388806126697916963123413431108069961369055630747412550900239402710827847917960870358653962948282381351741121884528399369764530446509936240262290248305226552117100584726616255292963971141510518678552679033220315246377746270515853987903184512948801397452104554589803725619076066339968999308910127885089547678968793196148780382182445270838659078189316664538631875879022325427220682805580410213245364855569367702919157881367085677283124732874621569379901272662162025780608669577546548333274766058755786449491277002349918598971841605936268030140638579388226573929

e= 2199344405076718723439776106818391416986774637417452818162477025957976213477191723664184407417234793814926418366905751689789699138123658292718951547073938244835923378103264574262319868072792187129755570696127796856136279813658923777933069924139862221947627969330450735758091555899551587605175567882253565613163972396640663959048311077691045791516671857020379334217141651855658795614761069687029140601439597978203375244243343052687488606544856116827681065414187957956049947143017305483200122033343857370223678236469887421261592930549136708160041001438350227594265714800753072939126464647703962260358930477570798420877

c = 5050700824254369629706222317182304817854328502946762466640160034518936104331190872577165966740698992599993738318065255426640532388783701269523249466457133362594746792709049331755573439792147596921989197734488068944429765799441691036386928330707210973914074578898342882873616545592434522483589258331701541867114404243232706375190196458540529576587657819733333494394523717323185402624115436179872398952968236327891601604027452104042607034392903007131961865175671712730843855271756666933385216702709156167983750382459620742910616481648578102406179645040011072888784105210037974451473774905783067038311390636241835590091


for phi in [
    phi[0]
    for k, d in [
        f.as_integer_ratio() for f in (e / N).continued_fraction().convergents()
    ]
    #if k != 0 and (phi := divmod(e * d - 1, k))[1] == 0
    if k != 0 and (phi := divmod(e * d - 1, k))
]:
    x = PolynomialRing(RationalField(), "x").gen()
    if len(roots := (x ** 2 - (N - phi + 1) * x + N).roots()) == 2:
        print(
            long_to_bytes(
                pow(c, inverse_mod(e, (roots[0][0] - 1) * (roots[1][0] - 1)), N)
            )
        )

扩展Wiener攻击

Everything is Still Big

N = 0x665166804cd78e8197073f65f58bca14e019982245fcc7cad74535e948a4e0258b2e919bf3720968a00e5240c5e1d6b8831d8fec300d969fccec6cce11dde826d3fbe0837194f2dc64194c78379440671563c6c75267f0286d779e6d91d3e9037c642a860a894d8c45b7ed564d341501cedf260d3019234f2964ccc6c56b6de8a4f66667e9672a03f6c29d95100cdf5cb363d66f2131823a953621680300ab3a2eb51c12999b6d4249dde499055584925399f3a8c7a4a5a21f095878e80bbc772f785d2cbf70a87c6b854eb566e1e1beb7d4ac6eb46023b3dc7fdf34529a40f5fc5797f9c15c54ed4cb018c072168e9c30ca3602e00ea4047d2e5686c6eb37b9
e = 0x2c998e57bc651fe4807443dbb3e794711ca22b473d7792a64b7a326538dc528a17c79c72e425bf29937e47b2d6f6330ee5c13bfd8564b50e49132d47befd0ee2e85f4bfe2c9452d62ef838d487c099b3d7c80f14e362b3d97ca4774f1e4e851d38a4a834b077ded3d40cd20ddc45d57581beaa7b4d299da9dec8a1f361c808637238fa368e07c7d08f5654c7b2f8a90d47857e9b9c0a81a46769f6307d5a4442707afb017959d9a681fa1dc8d97565e55f02df34b04a3d0a0bf98b7798d7084db4b3f6696fa139f83ada3dc70d0b4c57bf49f530dec938096071f9c4498fdef9641dfbfe516c985b27d1748cc6ce1a4beb1381fb165a3d14f61032e0f76f095d
c = 0x503d5dd3bf3d76918b868c0789c81b4a384184ddadef81142eabdcb78656632e54c9cb22ac2c41178607aa41adebdf89cd24ec1876365994f54f2b8fc492636b59382eb5094c46b5818cf8d9b42aed7e8051d7ca1537202d20ef945876e94f502e048ad71c7ad89200341f8071dc73c2cc1c7688494cad0110fca4854ee6a1ba999005a650062a5d55063693e8b018b08c4591946a3fc961dae2ba0c046f0848fbe5206d56767aae8812d55ee9decc1587cf5905887846cd3ecc6fc069e40d36b29ee48229c0c79eceab9a95b11d15421b8585a2576a63b9f09c56a4ca1729680410da237ac5b05850604e2af1f4ede9cf3928cbb3193a159e64482928b585ac

s = floor(sqrt(N))
M = Matrix([[e, s], [N, 0]])
Mred = M.LLL()
D = [abs(Mred[i, 1]) // s for i in [0,1]]

for d in D:
    t = randint(2, N - 2)
    tt = pow(t, e, N)
    if tt^d != t:
        continue
    flag = int(pow(c, d, N))
    flag = flag.to_bytes((flag.bit_length() + 7)//8, 'big')
    print(f'FLAG: {flag.decode()}')