安全科普 | 从CTF中初认识RSA

2017-11-20 +12 235702人围观 ,发现 6 个不明物体 新手科普

前言

在我们在做CTF的密码学解题时,我们经常能发现,题型无非就是对称密码、不对称密码这些老生常谈的考点,RSA更是出题人最喜欢的知识点。那么什么是RSA,让我们用浅显的语言和题目来初步认识吧!由于自身只是一名初级选手,在讲述的过程中如有不准确甚至错误的地方,还望各路大牛批评指正!

正文 

RSA算法介绍

安全科普|从CTF中初认识RSA

RSA是一种非对称加密算法,它由 公钥(n/e),私钥(n/d),明文M和密文C组成。我们做CTF题目时,一般题目中会给出公钥和密文让我们推出对应的私钥或者明文。RSA的相关公式都写在上面脑图中,在正式讲解RSA加密算法前我们先来普及一波数学的基本知识。

RSA的算法涉及三个参数,ne1e2

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

e1和e2是一对相关的值,e1可以任意取,但要求e1与(p-1)*(q-1)互质;再选择e2,要求

(e2×e1)≡1(mod(p-1)×(q-1))。

(n,e1),(n,e2)就是密钥对。其中(n,e1)为公钥,(n,e2)为私钥。

RSA加解密的算法完全相同,设A为明文,B为密文,则:

A≡B^e2( mod n);B≡A^e1 (mod n)

(公钥加密体制中,一般用公钥加密,私钥解密)

e1和e2可以互换使用,即:

A≡B^e1 (mod n);B≡A^e2( mod n)

RSA加解密算法

小结一下上文

密文=明文的e指数 mod n   公钥 = (e,n)

明文=密文的d指数 mod n   私钥 =  (d,n)密钥对 (e,d n)

求n

准备两个质数p,q。这两个数不能太小,太小则会容易破解,将p乘以q就是n

n=p × q

求L

L 是 p-1 和 q-1的最小公倍数

L= lcm ( p -1 ,q - 1)

求e 

E必须满足两个条件:E是一个比1大比L小的数,E和L的最大公约数为1 

用gcd(X,Y)来表示X,Y的最大公约数则E条件如下

1 < e < L
gcd ( e , L ) =1

求d

求D也必须满足2个条件:

1 < d < L,e × d mod L = 1

CTF RSA 算法题目详细讲解

第一题    已知p、q、e求d

题目链接 : http://www.shiyanbar.com/ctf/1828

题目描述:

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17

求解出d

此题告诉我们 p、 q 、e

根据上面的方式求 d 脚本附下

安装好gmpy2库,python3搞定:

    p, q, e = gmpy2.mpz(473398607161), gmpy2.mpz(4511491), gmpy2.mpz(17)
    phi_n = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi_n)
    print(d)

第二题  已知p、q、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1979

题目:

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

c 是密文 已知 p、q、e 求明文

由上文得先求d 然后用解密的上文 数学公式 python 脚本附下

import gmpy2

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483L

q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407L

e = 65537L

c= 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034L

phi = (p - 1) * (q - 1)

# 计算得到私钥(n, d)

d = long(gmpy2.invert(e, phi))

n = p * q

# 计算并输出c^d mod n

print pow(c, d, n)

第三题   已知n、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1918 

安全科普|从CTF中初认识RSA

从题目中已经得 n 和e 

然后这里我们可以有几种方法求得p、q 

因式分解 n 用yafu 

使用yafu:链接:http://pan.baidu.com/s/1croXpO 密码:w43p

yafu使用方法

使用cmd进入yafu的解压目录(为了方便的话,自己可以把该目录加入到环境变量。)

输入yafu-x64进入命令行

最常用的命令是factor(n),将n值分解

得到p q 后求d  用 c(密文)的d次方模n得到明文

分解求得 n e 我们也可以用 github 上面的一个开源项目 求d

分解公钥得n、e的值,然后求解d,这边提供另外一种求解d的方案,就是利用github上的一个开源项目

github: https://github.com/pablocelayes/rsa-wiener-attack

安全科普|从CTF中初认识RSA

Python 脚本

#快速幂取模
def expMod2 (x, y, k ):  
    MASK = 0xffffffff  
    tx = x  
    modRes = 1  
    tx %= k  
  
    while (y&MASK):  
        if (y&1):  
            modRes = modRes * tx % k;
              
        y = (y>>1);  
        tx = tx * tx % k;  
    return modRes  

def toStr(i):
    result = ""
    while i!=0:
        result = chr(i % 256) + result
        i = i/256
    return result

B = [
     704796792,
752211152,
274704164,
18414022,
368270835,
483295235,
263072905,
459788476,
483295235,
459788476,
663551792,
475206804,
459788476,
428313374,
475206804,
459788476,
425392137,
704796792,
458265677,
341524652,
483295235,
534149509,
425392137,
428313374,
425392137,
341524652,
458265677,
263072905,
483295235,
828509797,
341524652,
425392137,
475206804,
428313374,
483295235,
475206804,
459788476,
306220148, 
     ]
n = 920139713
d = 96849619
result = ""
for b in B:
    a = expMod2(b, d, n)
    result += toStr(a)
    
print result

*参考来源:从数盲到口算 ——带你玩转RSA加密算法(一),作者漏斗社区

*本文作者:淼淼兮与怀;转载请注明来自 FreeBuf.COM。

发表评论

已有 6 条评论

取消
Loading...
css.php