一大波RSA就要来了~~

Swing

2016-09-10

Summary

Crypto, RSA

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

RSA–求d

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

求解出d

将得到的d提交：

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

自己代码解决笨办法

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模块解决

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那么就可以拿到私钥了

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

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密码

直接给脚本

#!/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不同其实我们可以用共模攻击

原理不说直接给脚本

# -*- 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然后开三次方，直接写代码爆破
这里直接用白师傅写的的脚本

#!/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 = (((-4pby4) + 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), -D2):
#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$。六模量，六个密码文本！

# -*- 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