RSA攻击手法及相应例题解析

发表于:2018-10-10 10:17:22 来源:  合天网安实验室 阅读数(0人)

RSA加密基本原理


加密过程


选择两个大素数p和q,计算出模数N = p * q


计算φ = (p−1) * (q−1) 即N的欧拉函数,然后选择一个e (1

取e的模反数为d,计算方法: e * d ≡ 1 (mod φ)


对明文A进行加密:B≡A^e (mod n) 或 B = pow(A,e,n),得到的B即为密文


对密文B进行解密,A≡B^d( mod n) 或 A = pow(B,d,n),得到的A即为明文


p 和 q :大整数N的两个因子(factor)


N:大整数N,我们称之为模数(modulus)


e 和 d:互为模反数的两个指数(exponent)


c 和 m:分别是密文和明文,这里一般指的是一个十进制的数


一般有如下称呼:


(N,e):公钥


(N,d):私钥


加密分析


RSA算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。


RSA的算法涉及三个参数,n、e、d。


其中,n是两个大质数p、q的积,n以二进制表示时所占用的位数,就是所谓的密钥长度。


e和d是一对相关的值,e可以任意取,但要求e与(p-1)*(q-1)互质;再选择d,要求(e*d) ≡ 1(mod(p-1)×(q-1))。


令φ = (p-1)(q-1) 上式即 d*e = 1 mod φ 即:(d*e - 1)% φ = 0, (n,e),(n,d)就是密钥对。其中(n,e)为公钥,(n,d)为私钥。 RSA加解密的算法完全相同,设A为明文,B为密文,则:A≡B^d( mod n);B≡A^e (mod n);(公钥加密体制中,一般用公钥加密,私钥解密) e和d可以互换使用,即:


A≡B^e (mod n);B≡A^d( mod n);


附加解释


同余符号 “ ≡ ”


数论中的重要概念。给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余, 记作a≡b(mod m)。对模m同余是整数的一个等价关系


比如26≡14(mod 12)


互质


公约数只有1的两个数,称为互质


RSA常见攻击及分解方法


RSA的非对称体制是建立在大整数分解难题上的,所以最基本的攻击方法就是当模数N过小时,直接计算它的因子。但是大部分情况下稍微有点难度的rsa题目都不会是直接暴力分解N,而是需要一定的攻击手法。


N如果是256bits可以直接分解,如果超过了就基本别想暴力分解了,需要用到下面的一些攻击手法,下面列举一下一些攻击手法。


Wiener’s attack


当 d < (1/3) N^(1/4)时,我们可以通过Wiener’s attack分解得到d


费马分解


当大整数N的两个因子p和q相近时,我们可以通过费马分解的办法很快分解大整数


Small q


当q较小时,即|p-q|较大时,我们可以直接爆破因子


Boneh Durfee Method


当d满足 d ≤ N^0.292 时,我们可以利用该方法分解N,理论上比wiener attack要强一些。


yafu


yafu使用最强大的现代算法去自动化的分解输入的整数。大多数的算法都实现了多线程,让yafu能充分利用多核处理器(算法包括 SNFS, GNFS, SIQS, 和 ECM)。


factordb


如果对一个大整数用一些特殊算法也分解不了的时候,我们可以在 http://factordb.com/ 中查询一下数据库,说不定就能找到其因子


先看一个可以直接分解来解决的例题


看完攻击手法,我们拿例题来更好的认识一下攻击手法。


medium RSA


下载地址: https://dn.jarvisoj.com/challengefiles/mediumRSA.rar.07aab25c9c54464a8c9821ca28503330


给出两个文件:


flag.enc
pubkey.pem

可以看到一个公钥,一个加密后的文件


正常分解的解决方法


openssl分解公钥得到N、E


				   	@Archerx MINGW64 ~/Desktop/mediumRSA
$ openssl rsa -pubin -text -modulus -in pubkey.pem
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: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----
writing RSA key
可以看到N(256bits)很短直接分解即可(几分钟之内)
yafu-x64.exe factor(0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD)


fac: factoring 87924348264132406875276140514499937145050893665602592992418171647042491658461
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C77
rho: x^2 + 2, starting 1000 iterations on C77
rho: x^2 + 1, starting 1000 iterations on C77
pm1: starting B1 = 150K, B2 = gmp-ecm default on C77
ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default
ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default
ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec

starting SIQS on c77: 87924348264132406875276140514499937145050893665602592992418171647042491658461

==== sieving in progress (1 thread):   36224 relations needed ====
====           Press ctrl-c to abort and save state           ====
36365 rels found: 18303 full + 18062 from 192045 partial, (1292.02 rels/sec)

SIQS elapsed time = 164.9998 seconds.
Total factoring time = 188.9755 seconds

				   	
				   	***factors found***

P39 = 275127860351348928173285174381581152299
P39 = 319576316814478949870590164193048041239

ans = 1
				   	

python代码生成私钥


				   	##python 2.7 环境

coding=utf-8
import math
import sys
from Crypto.PublicKey import RSA
keypair = RSA.generate(1024)
keypair.p = 275127860351348928173285174381581152299
keypair.q = 319576316814478949870590164193048041239
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 解密


@Archerx MINGW64 ~/Desktop/mediumRSA
$ openssl rsautl -in flag.enc -out flag.txt -inkey private.pem -decrypt -pkcs

RSActfTOOL


下载地址:https://github.com/Ganapati/RsaCtfTool


可以用公钥直接生成私钥


python RsaCtfTool.py --publickey pub.key --private > private.key


私钥解密:


➜ RSA openssl rsautl -decrypt -in flag.enc -inkey private.key -out flag.txt


低加密指数攻击


Extremely hard RSA


题目信息:没想到 RSA4096 都被你给破了,一定是我的问题,给了你太多信息,这次我只给你一个 flag 的加密值和公钥,仍然是 RSA4096,我就不信你还能解出来。


题目链接:


https://dn.jarvisoj.com/challengefiles/extremelyhardRSA.rar.8782e822c895a2af3d8ba4ffbb3e280b


解题思路:openssl 解码一下piblic.pem可以看到E=3(一般情况下E=0x10001),典型的低加密指数攻击


注:flag.enc以十六进制方式来读取,因为文件中含有很多不可打印字符。


				   	#python2.7

import gmpy2,binascii,libnum,time
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e=3
res=0
c=int(open('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
				   	

破电脑跑了快半个小时,期间以为卡了,还好跑出来了&……


另一道ctf


#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

正常e的值通常情况下是0x10001,上面这个e明显值过小,而且是3,所以还是低加密指数攻击


脚本如下:


import gmpy2,binascii,libnum,time
n=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
e=3
res=0
# c=int(open('flag.enc','rb').read().encode('hex'),16)
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
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

共模攻击


Very Hard RSA


题目链接:https://www.jarvisoj.com/challenges


题目给出加密代码如下:


#!/usr/bin/env python3
import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
	return ('', '0')[len(x)%2] + x

e1 = 17
e2 = 65537


fi = open('flag.txt','rb')
fo1 = open('flag.enc1','wb')
fo2 = open('flag.enc2','wb')


data = fi.read()
fi.close()

while (len(data)<512-11):
	data  =  chr(random.randint(0,255))+data

data_num = int(data.encode('hex'),16)

encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)


fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))

fo1.close()
fo2.close()

注:N后面的L是为了强制编译器把常量作为长整数来处理,只需在后边加上一个字母L(或l)


首先看这个N长度(4096bit)就别想暴力分解了。


代码可以看到是相同的N,不同的E加密的,那就使用共模攻击


解密代码如下:


#! /usr/bin/env python3
# -*- coding: utf-8 -*-
# Author: Archerx
# @time: 2018/9/11 下午 06:11


import gmpy2
def ByteToHex( bins ):
    return ''.join( [ "%02X" % x for x in bins ] ).strip()
def n2s(num):
    t = hex(num)[2:]
    if len(t) % 2 == 1:
        t = '0'+ t
    return ''.join([chr(int(b, 16)) for b in [t[i:i+2] for i in range(0, len(t), 2)]])
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
s = gmpy2.gcdext(e1,e2)     #gmpy2.gcdext(e1,e2)的运行结果为元组(mpz(1), mpz(30841), mpz(-8)),所以元组的第0个值不能取,第1个值才是s1,第2个值由于是负数,所以要取反,变为正数
s1 = s[1]
s2 = -s[2]
file1 = open("flag.enc1" ,'rb').read()
c1 = int(ByteToHex(file1),16)
file2 = open("flag.enc2" ,'rb').read()
c2 = int(ByteToHex(file2),16)
c2 = gmpy2.invert(c2, n)        #由于根据前面的运算,s1是正数,s2是负数,后面需要运算c2的s2次幂。因为在数论模运算中,要求一个数的负数次幂,与常规方法并不一样,比如此处要求c2的s2次幂,就要先计算c2的模反元素c2r,然后求c2r的-s2次幂。
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
print(n2s(m))

rabin算法


hard RSA


题目链接:https://www.jarvisoj.com/challenges


也是给了和上面一样的两个文件pubkey.pem和flag.enc


提取公钥发现e=2,N与上面medium rsa例题一样,用rabin算法(该算法只适合e=2的情况)


N在上面已经用yafu分解出来p,q了,直接用就可以了。


python脚本如下:


#!/usr/bin/env python2.7
# -*- coding: utf-8 -*-
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)
    # print cipher
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
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')

相关新闻

大家都在学

课程详情

信息安全意识教育

课程详情

小白入门之旅

课程详情

信息安全基础