第一次发主题帖，格式排版啥的大家将就着点
一、rsa算法简介
和rsa相关的参数无非就是n、p、q、e、c、m、d。
p、q为素数，p*q=n，d由p和q求出。c是密文，m是明文。
（n、e）就是公钥（n、d）是私钥。公钥是给其他人加密用的，只有有私钥才能解密。
（1）假设p=61、q=53
（2）n = 61×53 = 3233
（3）计算n的欧拉函数 φ(n) = (p-1)(q-1)
φ(3233)等于60×52，即3120。
（4）选择e 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
（5）使用扩展欧几里得算法求得d
（6）n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
rsa的可靠性就在于n如果十分大，不可分解p*q相乘的形式。
这里附上一段rsa解密用的python脚本
#coding:utf-8
def gcd(a, b): #求最大公约数
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
if __name__ == "__main__":
c =
p = 49891
q = 18443
n = p*q
e = 19
d = modinv(e, (p - 1) * (q - 1))
m=pow(c,d,n)
print m
二、Coppersmith定理攻击
下面开始正题，Coppersmith定理攻击，也是针对n
Coppersmith定理指出在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根。
这个定理可以应用于rsa算法。如果e = 3并且在明文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。
下面根据一个题目来讲解攻击方法
题目中一个加密的enc文件，一个私钥文件。使用openssl查看密钥中的信息。
但是我们发现，奇怪的是在两个素数p、q中只给出了一个，并且这一个后面还有好多0，看来是一个不完整的数。我们带入Coppersmith定理，满足，则可以使用该攻击方法。
这里附上sage脚本、sage是基于python的一个数学处理库
n=0x985CBA74B3AFCF36F82079DE644DE85DD6658A2D3FB2D5C239F2657F921756459E84EE0BBC56943DE04F2A04AACE311574BE1E9391AC5B0F8DBB999524AF8DF2451A84916F6699E54AE0290014AFBF561B0E502CA094ADC3D9582EA22F857529D3DA79737F663A95767FDD87A9C19D8104A736ACBE5F4A25B2A25B4DF981F44DB2EB7F3028B1D1363C3A36F0C1B9921C7C06848984DFE853597C3410FCBF9A1B49C0F5CB0EEDDC06D722A0A7488F893D37996F9A92CD3422465F49F3035FEA6912589EFCFB5A4CF9B69C81B9FCC732D6E6A1FFCE9690F34939B27113527ABB00878806B229EC6570815C32BC2C134B0F56C21A63CA535AB467593246508CA9F9
p=0xBCF6D95C9FFCA2B17FD930C743BCEA314A5F24AE06C12CE62CDB6E8306A545DE468F1A23136321EB82B4B8695ECE58B763ECF8243CBBFADE0603922C130ED143D4D3E88E483529C820F7B53E4346511EB14D4D56CB2B714D3BDC9A2F2AB655993A31E0EB196E8F63028F9B29521E9B3609218BA0000000000000000000000000
p_fake = p+0x10000000000000000000000000
pbits = 1024
kbits = pbits-576
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
print x0 + pbar
http://sagecell.sagemath.org/ 一个在线运行sage脚本的网站
其实在这里只需要知道576bit，即144位十六进制数便可以解出。
>>> len("BCF6D95C9FFCA2B17FD930C743BCEA314A5F24AE06C12CE62CDB6E8306A545DE468F1A23136321EB82B4B8695ECE58B763ECF8243CBBFADE0603922C130ED143D4D3E88E483529C820F7B53E4346511EB14D4D56CB2B714D3BDC9A2F2AB655993A31E0EB196E8F63028F9B29521E9B3609218BA")
231
这里还多给了不少。记得后面需要补0到1024bit。
求得p、然后n/p=q，知道了p和q，就可以生成私钥，来解密文件了
p=0xbcf6d95c9ffca2b17fd930c743bcea314a5f24ae06c12ce62cdb6e8306a545de468f1a23136321eb82b4b8695ece58b763ecf8243cbbfade0603922c130ed143d4d3e88e483529c820f7b53e4346511eb14d4d56cb2b7b3060a902751b836e36d4ce17042a2b4022b306e43f7b79b5fdf1bd216a24e4e6ec2b9a5c6d3b77f7cdL
q=0xce69cb9edfdd2fb10ba9604a3d62372a4c66cfa9a4d3fcab0cfb84c73542005eaa0c74fba8d6683b5448c25fa01fe6a7aac4fbc124b1a5cf09e42417b43924251a9a86edfedd9a3fdea47d9334b0d8771fee872a218dbec5d5dd760a8cb08e7b7903bce7e66c21ebdfe454edf98cb852a44caf29196caa089070efd6ff10b6ddL
生成私钥
解密文件
| 
[复制链接]
发表于 2017-10-19 13:28
