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

前言

在我们在做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加密算法(一),作者漏斗社区

editors

相关文章
发表回复