@iPhan 2017-12-13T13:41:37.000000Z 字数 5895 阅读 496

张一帆15180110001密码学实验_EX5

密码学

张一帆15180110001密码学实验_EX5

github账号

实验题目

RSA挑战？

实验摘要

有人制作了一个 RSA 加解密软件(采用的 RSA 体制的参数特点描述见密码背景部分)
。已知该软件发送某个明文的所有参数和加密过程的全部数据(加密案例文件详见附件 3-1)。Alice 使用该软件发送了一个通关密语,且所有加密数据已经被截获,请问能否仅从加密数据恢复该通关密语及 RSA 体制参数?如能请给出原文和参数,如不能请给出已恢复部分并说明剩余部分不能恢复的理由?

描述

用各种可能的针对RSA的攻击试试看

背景与原理与实验步骤

fermat攻击

费马攻击基于一个事实：如果RSA的参数p、q相差不大（|p-q| < N^(1/4)）时，可以通过费马分解法比较容易地分解N。

思路是：设

$a=1/2(p+q)$

$b = 1/2(p-q)$ 则有：

$N = (a+b)*(a-b) = a^2 - b^2$

所以我们可以通过遍历a，计算 $b^2 = N - a^2$ 并判断 $b^2$ 是否为完全平方数来判断是否得到了正确的 a和b。

代码如下[1]：

def is_sqrt(number):
    x = number
    y = (x + number // x) // 2
    while y < x:
        x = y
        y = (x + number // x) // 2
    return x
def isqrt(n):
    return int(n**.5)
def fermat(n):
    a = is_sqrt(n)
    b2 = a ** 2 - n
    b = isqrt(n)
    count = 0
    while b ** 2 != b2:
        a += 1
        b2 = a ** 2 - n
        b = isqrt(b2)
        count += 1
    p = a + b
    q = a - b
    assert n == p * q
    return p, q

通过设计定时，对全部的21帧进行排查，成功分解了Frame10的N：

N = 9686924917554805418937638872796017160525664579857640590160320300805115443578184985934338583303180178582009591634321755204008394655858254980766008932978699 * 9686924917554805418937638872796017160525664579857640590160320300805115443578184985934338583303180178582009591634321755204008394655858254980766008932978633

解有对应的明文为：

0x9876543210abcdef00000008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000077696c6c20676574

即：'will get'

RSA共模攻击

共模攻击是一种非常简单的攻击，简述如下：

对于 $C1 = M^a mod N$ , $C2 = M^b mod N$

计算 $s = inv(a) mod b$ , $t = (a*s-1)/b$ , $C2 = 1/C2$

即有： $M = C1^s * C2^t$

实现：

首先，通过检测21个帧中是否存在相同N来判断是否存在共模攻击，代码如下：

# 0和4有rsa共模
for key in cipher:
    for e in cipher:
        if cipher[key]['N'] == cipher[e]['N'] and key != e:
            print(key, '--', e)

发现Frame0与Frame4可能存在共模攻击。首先假设他们的明文相同，共模攻击代码如下：

def same_mod(e1, e2, c1, c2, n):
    r1 = inverse(e1, e2)
    r2 = (e1 * r1 - 1) // e2
    c2 = inverse(c2, n)
    m = pow(c1, r1, n) * pow(c2, r2, n)
    return m % n

解有Frame0，4的明文为：

0x9876543210abcdef0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004d79207365637265

即为：'My secre'

pollard

pollard基于这样的思路：对于 $N = p*q$ ，p-1没有很大的素因子时，存在比较小的整数k，使得：

$p-1|k!$

由欧拉定理，对于与p互素的随机值g，与 $t = p-1$ ，有：

$g^t = 1 mod p$

所以，对于 $y = k!$ 有

$p|g^y - 1 mod N$

所以此时只需要判断 $g^y -1$ 与N的最大公约数是否非1即可。当该最大公约数非1时，即为所求的p。代码如下：

from Crypto.Util.number import inverse, GCD
def pollard(n):
    a = 2
    k = 1
    while True:
        a = pow(a, k, n)
        k = k + 1
        p = GCD(a - 1, n)
        if p == 1:
            continue
        else:
            break
    return p

扫描21个帧，得到Frame2，Frame6，Frame19的N的分解：

Frame2
(1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111, 52484065122572767557293534477361686456679280880304125291106733197354892893647364164212186415880889674435558369420400890814461263958618375991691022752189839)
0x9876543210abcdef0000000600000000000000000000000000000000000000000000000000000000000000000000000000000000000000002054686174206973
' That is'
Frame6
(920724637201, 159482692259010816139523195494724350795654007589889398757383554027183924116413427533184220914037106543253535103452324841452565420868944985464229649420240708554088156331324206733727690785373464575525698274552058386560106163093965065830071277465943834308083708065429495092746028681968670036721164931)
0x9876543210abcdef00000007000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020224c6f67696320
' "Logic '
Frame19
(1085663496559, 86725761611859895386396141031497189948984447138542215420462553101081991008304507461163078354877970282649251051457532902955009856009405853917396630017011320500357081664483071782135584899953560478866041032397335990722689211113937797406269980402604895207480485168493674422769645640726941944110986793)
0x9876543210abcdef000000050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000696e737465696e2e
'instein.'

孙子定理

Frame3, 8, 16, 12, 20 存在相同明文&低加密指数攻击，其中加密指数为5，可以通过三个密文-公钥对利用孙子定理恢复出原始的明文。

孙子定理维基百科链接

孙子定理以及RSA恢复明文的实现代码[2]：

def lowE(c_list, n_list, e):
    gs = {}
    for i in range(len(c_list)):
        gs[i] = {}
        gs[i]['a'] = c_list[i]
        gs[i]['mi'] = n_list[i]
    M = 1
    for key in gs:
        M *= gs[key]['mi']
    for key in gs:
        gs[key]['Mi'] = M // gs[key]['mi']
        gs[key]['ti'] = inverse(gs[key]['Mi'], gs[key]['mi'])
    x = 0
    for key in gs:
        x += gs[key]['a'] * gs[key]['ti'] * gs[key]['Mi']
    x = x % M
    decimal.getcontext().prec = 154
    return hex(int((decimal.Decimal(x).ln() / decimal.Decimal(e)).exp()))

得到的明文：

0x9876543210abcdef0000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000007420697320612064
't is a d'

两个N最大公约数非1

对于两个不同的N，若他们的最大公约数非1，则说明他们共用同一个p。求最大公约数是非常容易的。扫描发现Frame1, 18 存在非1最大公约数

攻击代码：

from Crypto.Util.number import inverse, GCD
p1 = GCD(cipher['1']['N'], cipher['18']['N'])
q1 = cipher['1']['N'] // p1
assert p1 * q1 == cipher['1']['N']
fn1 = (p1 - 1) * (q1 - 1)
d1 = inverse(cipher['1']['e'], fn1)
m1 = pow(cipher['1']['c'], d1, cipher['1']['N'])
print('Frame1')
print((p1, q1))
print(hex(m1))
# '. Imagin'
p18 = p1
q18 = cipher['18']['N'] // p18
assert p18 * q18 == cipher['18']['N']
fn18 = (p18 - 1) * (q18 - 1)
d18 = inverse(cipher['18']['e'], fn18)
m18 = pow(cipher['18']['c'], d18, cipher['18']['N'])
print('Frame18')
print((p18, q18))
print(hex(m18))
#'m A to B'

得到的pq分解以及明文：

Frame1
(7273268163465293471933643674908027120929096536045429682300347130226398442391418956862476173798834057392247872274441320512158525416407044516675402521694747, 12775796067504534889308793837705093856447186276434607181291462366302734214583227473619414509043813033676998357747882057607288385639737162184366176530607467)
0x9876543210abcdef0000000b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000002e20496d6167696e
Frame18
(7273268163465293471933643674908027120929096536045429682300347130226398442391418956862476173798834057392247872274441320512158525416407044516675402521694747, 12840807874760119497562989864651565491645077946976950748211992253853323703532620362223764981952516328133916264333884385029280730688894521589959051436522977)
0x9876543210abcdef0000000a00000000000000000000000000000000000000000000000000000000000000000000000000000000000000006d204120746f2042

至此已给出了除随机数生成器以外的全部攻击

不太熟悉LSFR，现在借来了11班的密码书来看但是感觉今晚费劲能看明白论文中的“循环”是啥意思。。论文中对LSFR随机数生成器的攻击能做到复现，但是不理解原理。有些低估这个随机数生成器了。。待我看完再补可好。。

参考文献

RSA 加密体制破译报告——双河安团队答题卷

[1] 因为python中的pow函数只有53bits的精度，所以在这里手动实现了一个牛顿法求平方根的函数is_sqrt ↩
[2] 此处没有继续手动实现牛顿法，改用decimal这个库来进行高精度开5次方运算 ↩