Crypto学习笔记

线性同余(LCG)的攻击

LCG

LCG(linear congruential generator)线形同余算法,可以用来递归生成随机数。
$ X_{n+1}=(aX_n+c) mod m $
其中a,c,m为常数,可以看到生成算法的结构十分简单,要使LCG的最大周期是m需要:

1.GCD(c,m)=1

2.m的所有质因数都能整除a-1

3.若m是4的倍数,a-1也是

4.a,c,初始X都比m小

5.a,c为正整数

攻击方法

1.若a, c, m, X0 已知

若全部参数都已经知道,我们可以直接算出任意一个值

2.若c未知,但有连续两个X(X0, X1)

由定义我们有

$ X_{1}=(aX_0+c)mod m $

移一下就有

$ c=X_1-aX_0mod m $
代码

c = (x[1]-a*x[0]) % m

2.若a, c未知,但有连续的三个X(X0, X1, X2)

$ X_1=(aX_0+c) mod m $
$ X_2=(aX_1+c) mod m $
$ X_2-X_1=a(X_1-X_0) mod m $
$ a=(X_2-X_1)/(X_1-X_0) mod m $

a = (x[2] - x[1]) * inverse(x[1] - x[0], m) % m

有了a再求c用1中的方法就可以了

3.若a, c, m未知,但有连续的n个X(n>=4)

这个时候就不能解方程解出某些量了

我们的攻击思路是找到几个数Y满足
$ Y_i=k_im $
$ Y_i=0 mod m $
这样的几个Y的最大公因数是为m的(一定条件下),我们要做的就是用连续的n个X找到T

所以考虑这样一个序列
$ Tn= S{n+1} - S_n $

t0 = x1 - x0
t1 = x2 - x1 = (x1*a + c) - (x0*a + c) = a*(x1 - x0) = a*t0 (aod m)
t2 = x3 - x2 = (x2*a + c) - (x1*a + c) = a*(x2 - x1) = a*t1 (aod m)
就可以发现
Y0 = t2*t0 - t1*t1 = (a*a*t0 * t0) - (a*t0 * a*t0) = 0 (mod m)

同理我们有Y1, Y2...

然后求GCG(Y0,Y1, Y2...)即可,下面例子里面只要Y0,Y1就可以求出m。。。

from Crypto.Util.number import *

x = [2818206783446335158, 3026581076925130250, 136214319011561377,
     359019108775045580, 2386075359657550866, 1705259547463444505]

# 求模数m
t = []
for i in range(5):
    t.append(x[i+1]-x[i])
y = []
for i in range(3):
    y.append(t[i+2] * t[i] - t[i+1] * t[i+1])
m = GCD(y[0], y[1])
# 求乘数a
a = (x[2]-x[1])*inverse(x[1]-x[0], m) % m
# 求增量c
c = (x[1]-x[0]*a) % m

# 验证
print(a, c, m, x[0])
_x = [x[0]]
for i in range(5):
    _x.append((x[i] * a + c) % m)
print(_x)

希尔密码

基本原理

希尔密码是用矩阵实现的一种代换密码。

明文和密文是两个同型矩阵,解密密钥是加密密钥模26的逆元。
$ C= Menkey (mod 26) $
$ dekey= enkey^{-1} (mod 26) $
$ M= Cdekey (mod 26) $
求dekey(keyinv)解的时候代码如下

keyinv = mod(modinv(det(key), 26) * det(key) * inv(key), 26)

一些问题

1.不难看出,key必须是n阶方阵,M要求是列数n的矩阵

2.key在选取时需要可逆

3.若同时知道n^2长度的明密文,就可以先求出key

例子

m已知是7,4,2;19,5,4;25,19,7(HECTF...)c已知为2,3,16;18,17,15;15,22,20(没什么意义的字母串),那么就有

>> m=[7,4,2;19,5,4;25,19,7];
>> c = [2,3,16;18,17,15;15,22,20];
>> key = mod(mod(modinv(det(m), 26)*inv(m)*det(m)*c, 26);
>> keyinv = mod(modinv(det(key) * det(key) * inv(key) ,26);
>> cc = [2,3,16;18,17,15;15,22,20;25,25,24;9,7,22;17,7,24;25,17,8;15,5,15;23,14,11];
>> mm = mod(cc*keyinv, 26);

​ 就可以从前9位m还原出整个m

希尔密码的其他形式

​ 对怎么将写成矩阵形式也是我们需要考虑的一部分。在上面的例子中,我们是直接把m按行的顺序写上去的,但实际上在加密时,m可以按列来写,这样我们知道的前n^2位就不能解出key。另外,我们使用的是M右乘key,其实也可以是左乘(实际上是一样的)。希尔密码利用线性变换,能够较好地抵抗频率分析,很难被频率分析攻破,安全性还是比一般的古典密码要强一些的,但线性变换本身是脆弱的。

两个简单的分解整数的方法

Pollard p-1 方法

费马小定理

​ 若p是素数,a不是p的倍数,则有
$ a^{p-1}= 1 (mod p) $

B-Smoth数

如果一个正数的所有因子都不大于B,就称这个数是B-Smoth的

原理

若p-1是B-Smoth的数,且p-1的任意两个因子都不相等,则有
$ a^{B!}= a^{k(p-1)} = 1 (mod p) $
N=p*q,,我们要做的是找一个B,让a^{B!}-1=kp,若 1 < GCD(a^{B!-1}, N) 1,GCD算法的复杂度还是比较低的。Pollard ρ的概率性体现在随机选取c*sqrt(p)个整数(c是一个常数),就有很大概率能找到两个数模p相等。
$ X_j = X_i (mod p) $
$ GCD( X_j-Xi,N)=p $
实际上找这两个数的时候,是使用下面的同余式来“随机”选取两个数,一般$ f(n)=n^2+a $,a为一个随机数
$ X
{i+1} = f(X_i) (mod p) $
但这个递推序列在mod p的意义下一定是循环的,形似ρ。

rho

Floyd 判环

Floyd 是一种判断序列元素是否重复的方法,当然,我们可以把所有的X存下来,但这样占内存太多了,Floyd 只需要常数个空间,具体是让j以两倍i的速度走这个环,若 $ X_j = X__i $,就可以说i已经至少走了这个环一圈。

在Floyd 判环下的pollard ρ实现

def f(x):
    x = (x*x + 1) % n
    return x

# x1, x2
def pollard_rho(x1, x2):
    while True:
        x1 = f(x1)
        x2 = f(f(x2))
        p = GCD(x1-x2, n)
        if p == n:
            return
        elif p != 1:
            return p, n//p

# test
n = 5929283*4338011
print(pollard_rho(2, 2))
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇