一大波RSA就要来了~~

<–more–>

先不说RSA原理 我也懒得重复的造轮子

RSA–求d

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

求解出d

将得到的d提交:

题目很简单 有取巧的方法 也有笨方法

自己代码解决 笨办法

1
2
3
4
5
6
7
8
9
10
11
p = int(raw_input("Enter a p: "))   
q = int(raw_input("Enter a q: "))
e = int(raw_input("Enter a e: "))
t = (p-1)*(q-1)
i=0
while True :
if (1-t*i)%e == 0:
break
i-=1
print i
print 'ok:' + '%d' % ((1-t*i)/e)

脚本写得老粗糙

python模块解决

1
2
3
4
5
import gmpy2
p = int(raw_input("Enter a p: "))
q = int(raw_input("Enter a q: "))
e = int(raw_input("Enter a e: "))
gmpy2.invert(e, (p-1)*(q-1)) `

别人已经写好的工具 即rsatool.py

1
rsatool.py -p 473398607161 -q 451149 84376578389 -e 17

基础求明文-N已经被分解

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

某个明文加密后的结果为:727835100378484285
将得到的明文提交:
既然以及有了p,q那么就可以拿到私钥了

1
2
3
4
5
6
7
8
9
10
11
12
rsatool.py -p 473398607161 -q 4511491 -e 17
Using (p, q) to initialise RSA instance

n = 2135733555619387051 (0x1da3a65a6d9356ab)

e = 17 (0x11)

d = 125631357777427553 (0x1be550de4f93c61)

p = 473398607161 (0x6e38c17d39)

q = 4511491 (0x44d703)

1
2
print ('%x' % pow(727835100378484285,125631357777427553,2135733555619387051)).decode('hex')
testMe!

基础求明文-N未被分解

N = 322831561921859, e = 23,cipher = 0xdc2eeeb2782c

题目没有上一题给的p,和q,所以得对N进行分解

yafu配合rsatool.py + python

这个题目和上面题目的区别就是N没有被分解 用yafu这个工具可以进行大数字分解

然后剩下的方法和上面差不多就不累加叙述了

512位的大家伙

你没看错,这还真是密码学系列了,相信你已经解出前两题了,那么继续看这题吧。
链接:http://pan.baidu.com/s/1o77LozK 密码:1ik4

这个题目第一次遇到的时候我碰到了一个麻烦 就是不知怎么提取公钥
两个方法

Python解决

利用python的Crypto

1
2
3
4
from Crypto.PublicKey import RSA
A = RSA.importKey(open('pem文件名字').read())
A.n
A.e

如图 就得到了公钥

然后剩下的步骤依旧就是 分解N 生成私钥 解密

openssl解决

提取公钥

1
openssl x509 -outform PEM -in server/server.crt -pubkey -out server/server.pubkey

hard RSA

相信你已经做出了medium RSA,这题的pubkey在medium RSA的基础上我做了点手脚,继续挑战吧。
Hint1: 1.不需要爆破。2.用你的数学知识解决此题。3.难道大家都不会开根号吗?
链接:http://pan.baidu.com/s/1kVxYmiV 密码:oix5

考验大家数学知识的来了

这个题目和上个题目的相同之处是 N是一样的 但是这个题目的 e = 2
e一样 这个题目应该是 Rabin密码

直接给脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import libnum
import gmpy2
f = open('flag.enc','r')
c = f.read()
c = libnum.s2n(c)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
r = pow(c,(p+1)/4,p)
s = pow(c,(q+1)/4,q)
a = gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
x =(a*p*s+b*q*r)%n
y =(a*p*s-b*q*r)%n
print libnum.n2s(x%n)
print libnum.n2s((-x)%n)
print libnum.n2s(y%n)
print libnum.n2s((-y)%n)

Very Hard RSA

前几题因为N太小,都被你攻破了,出题人这次来了个RSA4096,是否接受挑战就看你了。
链接:http://pan.baidu.com/s/1jIq8IKA 密码:k43g

对于这个题目 我们会发现 是用相同的N,不同的e进行加密的

这里有个技巧 如果我们发现 N相同 e不同其实我们可以用共模攻击

原理不说 直接给脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# -*- coding: utf-8 -*-

from libnum import n2s,s2n
from gmpy2 import invert

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 main():
# 输入参数
# fo1 = open('flag.enc1', 'rb')
# fo2 = open('flag.enc2', 'rb')
# c1 = fo1.read()
# c2 = fo2.read()
n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211
c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853
c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
e1 = 1804229351
e2 = 17249876309
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = invert(c1, n)
elif s2<0:
s2 = - s2
c2 = invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print n2s(m)

if __name__ == '__main__':
main()

Extremely hard RSA

没想到RSA4096都被你给破了,一定是我的问题,给了你太多信息,这次我只给你一个flag的加密值和公钥,仍然是RSA4096,我就不信你还能解出来。
链接:http://pan.baidu.com/s/1skBIUuD 密码:xvfr
题目的重点是:
公钥中,e=3,N非常大。所以可以不断地c+N然后开三次方,直接写代码爆破
这里直接用白师傅写的的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'ByStudent'
from libnum import s2n,n2s
from gmpy2 import iroot
n = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e = 3
f = open('flag.enc','rb')
c= f.read()
c = s2n(c)
f.close()
i = 0
while 1:
res = iroot(c+i*n,3)
if(res[1] == True):
print res
break
print "i="+str(i)
i = i+1
#i=118719487
m = 440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186
print n2s(m)
# 结果
# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}

Gold LIke RSA

这个题是到最后 i春秋把汪师傅的题上上去之后我才终于做出来的

既然你逼我到绝境,那就休怪我不客气了,代表上帝挑战你~
链接:http://pan.baidu.com/s/1qX7HmyS 密码:4vjz

后来才知道这个题是PCTF的一道题目改的 原题地址
先停在这 明天在写

RSANG

尝试着对N分解
模量对数
看起来像形式的数字$N = (2^M + a)(2^M + b)(2^M + c)(2^M + d) $.
日志基 2 的弹性模量是 5568 所以$M=1392$.
我们现在可以做一些数学,看看什么信息,我们可以摆脱 4 二进制序列︰

$$ N = (2^M + a)(2^M +b)(2^M +c)(2^M +d) $$

$$ N = 2^{4M} + 2^{3M}(a + b + c + d) + 2^{2M}(ab + ac + ad + bc + bd + cd) + 2^M(bcd + acd + abd + abc) + abcd $$

让︰
$$ p = a + b + c + d $$

$$ q = ab + ac + ad + bc + bd + cd $$

$$ r = bcd + acd + abd + abc $$

$$ s = abcd $$

你会忍不住想上述 4 的二进制字符序列对应直接到$p$, $q$, $r$, $s$ ,但这里面有蹊跷︰ 只有$s$等于其各自的二进制序列。
其他的可能会在 0 或更多,因为奇数偶数有甚至总和。我们可以只是强制性,但它,所以我们会担心以后。
我们如何找出$a$, $b$,$c$和$d$给定$p$, $q$, $r$ , $s$?高中数学的救援︰

$$ (X - x_1)(X - x_2)(X - x_3)(X - x_4) = 0 $$

$$ X^4 -(x_1 + x_2 + x_3 + x_4)X^3 + (x_1 x_2 + x_1 x_3 + x_1 x_4 + x_2 x_3 + x_2 x_4 + x_3 x_4)X^2 - (x_2 x_3 x_4 + x_1 x_3 x_4 + x_1 x_2 x_4 + x_1 x_2 x_3)X + x_1 x_2 x_3 x_4 = 0 $$
import math
import gmpy2
gmpy2.get_context().precision=5000
from polycubicroot import *
def Carpenter(p, q,r, s):
p = gmpy2.mpfr(p)
q = gmpy2.mpfr(q)
r = gmpy2.mpfr(r)
s = gmpy2.mpfr(s)
“””
Solves for all roots of the quartic polynomial P(x) = x^4 + px^3 + qx^2 + rx + s.
“””

#print “@@@ inside Carpenter”, p,q,r,s
pby4 = p/4.0
C = ((6 pby4) - 3p)pby4 + q
D = (((-4
pby4) + 3p)pby4 - 2q)pby4 + r
E = (((pby4 - p) pby4 + q)pby4 - r)*pby4 + s

#print “C, D, E=”,C, D, E
root = None
for zero in polyCubicRoots(2C, (C**2 - 4E), -D**2):

#print “zero = “, zero
if type(zero)== type(gmpy2.mpfr(1.0)) and zero > 0.0:
root = zero

#print “found a positive root.”
break
if root == None:
return None
sqroot = gmpy2.sqrt(root)
Q1 = -root/4.0 - C/2.0 - D/2.0 / sqroot
Q2 = -root/4.0 - C/2.0 + D/2.0 / sqroot

#print “Q1,Q2=”, Q1, Q2
sqy2 = sqroot/2.0
if Q1 >= 0.0:
sqQ1 = gmpy2.sqrt(Q1)
z1 = sqy2 + sqQ1 -pby4
z2 = sqy2 - sqQ1 -pby4
else:
sqQ1 = gmpy2.sqrt(-Q1)
z1 = (sqy2-pby4, sqQ1)
z2 = (sqy2-pby4, - sqQ1)
if Q2 >= 0.0:
sqQ2 = gmpy2.sqrt(Q2)
z3 = -sqy2 - sqQ2 -pby4
z4 = -sqy2 + sqQ2 -pby4
else:
sqQ2 = gmpy2.sqrt(-Q2)
z3 = (-sqy2-pby4, sqQ2)
z4 = (-sqy2-pby4, -sqQ2)
return (z1, z2,z3, z4)
得到一个 4 元组解和循环的左侧和右侧的任何 4 根,看看是否我们得到的除数$s$,应完全$a b c d$。如果我们得到一个然后基本上解决问题。
剩下的唯一问题是,我们不知道多少零点的每个$p$, $q$ ,$r$有。让我们试着从 3 零 0 零的所有组合︰
p= 0b10001110000110111100100111111000100111
q= 0b1110110010101000100001010011110000010100100010111011100111100011010001010101
r= 0b1010111100101001100011011101101000000110011010100010001010001100010000111001010011110111011000110010000110010001
s= 0b11000010011110000010000010000101010000011101100011101110110110011111000000001011001101111100111001111110001100100101101010011011011101110111001110101
A=[]
B=[]
C=[]
D=[s]
for i in range(0,3):
A.append(p (2**i))
B.append(q
(2i))
C.append(r * (2
i))
for i in A:
print “====================”
for j in B:
for k in C:
for l in D:
(x1, x2, x3, x4) = Carpenter(-i,j,-k,l)

since sometimes the solution will consist of complex numbers, we’ll just disregard those with a try-except

try:

#approximate value of x1
aprox = int(x1.floor())
for step in range(0,10000):

#try to the right
if s % (aprox + step) == 0:
print aprox + step

#and to the left
if s % (aprox - step) == 0:
print aprox - step
except:
pass

这样我们得到了所有的四个因素 !让我们看一下这些实际上将弥补$N$. 而且刚好对应6个密文
通常情况下,密文的内容有关于同一密钥作为弹性模量,但在这种情况下他们不。这意味着,要么

指数是小 (说 3) 和消息$m$是真的很短。但然后还有一个主要的问题︰ 因为根本不会被加密明文$m^3$将小于$N$所以$ m^3 $等于$ m^3 \bmod N $(没有加密 = = 坏)
指数是一个体面的大小 (通常是 65537) 但模量不是$N$。那么它是什么?提示︰ 密码密钥,大约是一半的模量。
由于有 4 质数我们可以作出以下模量︰ $ab $ $ ac $ $ ad $ $ bc $ $ bd $ $ cd$。六模量,六个密码文本 !

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# -*- coding: utf-8 -*-
import gmpy2
f1 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686599733
f2 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686598461
f3 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686597791
f4 = 108082147276398906822234149167480016132157014049560913761488880190018027488520386318253742675423286348552334110023434741671427911613197684395221211646299519273129194692306445874938199068586137486874290442314459278649345469626426790676801658394799404284116771456479272808343825651929906737811050557836671896732124546721747709022607151231423494815945385193624295868730390462068156825588342737037490320356361648437686600843

e = 65537


N = 136463296143190893248608270448493439350683115492680876168052084053504347848230208722375209906076869052896867483336405778205506777456239889195254751404720423599579856449118314029926341504368322006603240157122006887052352260584975471045726061549619820648607756554188235927302932154082823424745427535138517580059079182622982686168676727690710935334448342460007367100561867135456783067679052102951400317012276135721843672557488711786097028300122487504246207343408690682175135816894247936690735246673985277504237071409859401185555290479154689954442396078547166388871978321863215123445269948324347122830270551854130365741961149443091305418900821360286967705810624380568422193310901491451664233271486835428015602712828527839237760712498204208114606471362410690870710499020885304151928570632315330437235330924071236528549152143092328833484016372976817809299430339752106123272706667690980774118545338761390919046832338928913059106351087015273177895380149217373395580948428521961929052291618261409715145038026920685297885235683434107218249548518659574493203836870070093674704878498465104238178877833471640168999551981025958271865584457582649595664499635489167898398826429084686279399959537724187268210760718340639939389766681703213695409551029265784749153180083564347733676434492122290166926822855552175712346350104533901079605669192289178418165584907326210349152609265563881542151049862642882025360604692084264752182798892702414638180781403398216616666472863758371330058299406233359567750413748257953598843651612399709945608339073191578573877985362619301768016485017815171486743934037935902150228210340093187387036580763941637989511155597643722984057627086517479392172108031663245553269

enc_1 = 7106898334865955962704663230185766445951889978440527670379641714370681285859949869949187832359082523864224641583685587358279064795569170851524374568027152395396233789347594775999482749460592054691082921627513982308507181335532299134140407681024881476418889411780375090299905813982101694827597560498543197874412334623795312307111560405270260391658994764065881380399694265015620683173527502434421206862766543229116921174206929733891873772589067987314963792051855633244006474202333168597001157421208180748203884266562430752691702675420434792273754214010918653607624500201387229281379420620532777072560178585294886033718995698223904867539921848198115466603585461755489085844144950962514847839122794545452937035169471880080923607755994138855467643267829059636266176328056201003864357129609343207959211080595752950950566686954867562406898169012

enc_2 = 6049049661741129561339303988250162617703359741970199356749378099535308799521119296163475813567458644038456685905251522625056377260310087845057811228022836098917570328692580410899852889868960996513905266043335963520913743708134923879544500911079066640658342641576456724637857109609913138972587873848795314132791317122747052648231297078735128282339170389129703582587817548539040826603188468662975329145727078616857156409325283263490433476018586450960082502578543327451065633585123695731081960986876439520499678158646526292218543279767834119677467758578802705169018711527506297869276113561542222807369071584959189923897216079505316482443445467837921144205079761354928950270172051270453170856002545491432278972735662895438668870901370521394906635478044848448535690635490093836659267778026686404695474454443310769209580317339039949689309577128

enc_3 = 9297802808564228678857927735224258610176831223455462482108153962953283311112501933779642540831558523911908205264682548531027493458025348252477502958948277516597689610204247227516319189048436710254675204218913508162139428248916620471317757210444645620644754294112426431692939788347835259617673728076204145049918767636122119264147566892091600628134179775710906591426338082246629946748851355701691716873854064848390273287305765646761438968986164159947841015011854342290060053810459830057357847548324695563067411557873081187572229935066117850179208775004384867270372650455853756560763012162682268812544173997311505136324203900399349629488710197844813293107115270398692552357803651576615589484454781227778727051440858478438251726051391317986762487421941570502251822920317312304622541764818356928105898291743494415190324388360012261032469805293

enc_4 = 713095983409993528016630065648951013409887429450761159296479210782308084847050785300379490902448647458053364322993274237841476340954537003347555548992827654062094884577630320399338426853024680425709980978726290825928571411715417634212022523987025390940108095446209802316068849127107378425087055832984628808129531097287891984529260048649164000341136589805930287941174070455962380115617312855801447326371361475429811263285218112383055283949280091896985779211927696867430269968278138068400828124612158603851472016327854927370226178776190765638542240547246882872033038792494915187774790763271179846203704834184269540668646905004118327597860873987248913148268250014480899515845595580486997925049895214602419037682253683176691877538075243485739730794370764108792093424342949560517002862934953109055108423633725444594683266260073663364732952255

enc_5 = 10309778311674135836145162475142299890445328570998831868156889990227275287204954712195141311549279047953844775828171871944522109110470024787792366772581241453340259883183812924297131077506375091086889140550405275547002202216935333211274901846970064522877611909017778486075399188006657623263902100044828896866180655435221665929435914366779334701622735670714649165956831390471034827078404866534094264914677879030956272977839491780410171625330771079943455183946885337962048237633491024513227027839179415230496573264968451527246966618074421625677382526573096067979952606553854268016651712174361578916100364115941853700612277618158243626702349480460819792765645689509997114148748479096516230468934427015454217368508102362912163051749856763103972010705773880053579573724226945229453471505368052572019992934401394664840254259798167531746190494146

enc_6 = 8939535907261295438433886577386432968291926162277924912979941380189504000322310159787894619015550096747658897136943700072192920334615223423230154197591756541966832740944457435736068401948276698864982347929802551347213730712997519211436818145872722485367264219104124473346589051164722340414948298088909961344463800461486219156960782319672049123860381674970981713865865119998917955886468613202521879160392276542945726096267432761588212550950818569769983241315782390152313705093940640027041352082844550311829177150159737347964813330180325283882516072009654288888676591648012847062527444169352000893928289409020106115561912814987882374652419114381836807085680725260815445689968522849732254659773192714360607196619281714422460754645088867512471482029657153787836396684484646302575186890717770078233479877360251173401000006298555695416782863190

N = f3 * f4
phi = (f3-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_1, d, N))`[3:-1].decode('hex')

N = f2 * f4
phi = (f2-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_2, d, N))`[3:-1].decode('hex')

N = f1 * f4
phi = (f1-1)*(f4-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_3, d, N))`[3:-1].decode('hex')
N = f1 * f3
phi = (f1-1)*(f3-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_4, d, N))`[3:-1].decode('hex')

N = f1 * f2
phi = (f1-1)*(f2-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_5, d, N))`[3:-1].decode('hex')

N = f2 * f3
phi = (f2-1)*(f3-1)
d = gmpy2.invert(e, phi)
print `hex(pow(enc_6, d, N))`[3:-1].decode('hex')

最终简单的拿到了flag