題目如下：
首先：
驗(yàn)證工作
如何解乒躺，請(qǐng)看下面工作量證明算法
接下來(lái)：
圖片.png
選擇1 get code匣缘，得到加密腳本
選擇2，填充字符迫肖，得到密文
加密腳本如下：
#!/usr/bin/env python3
# -*- coding=utf-8 -*-
from Crypto.Util.number import getPrime, GCD, bytes_to_long
from hashlib import sha256
import random
import signal
import sys, os
signal.alarm(20)
m = b"xxxxxxxxxxxxxx"
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
e = 3
def proof():
strings = "abcdefghijklmnopqrstuvwxyzWOERFJASKL"
prefix = "".join(random.sample(strings, 6))
starwith = str(random.randint(10000, 99999))
pf = """
sha256("%s"+str).hexdigest().startswith("%s") == True
Please give me str
"""%(prefix, starwith)
print(pf)
s = input().strip()
if sha256((prefix+s).encode()).hexdigest().startswith(starwith):
return True
else:
return False
def cmd():
help = """
1. get code
2. get flag
Please tell me, what you want?
"""
while True:
print(help)
c = input().strip()
if c == "1":
return True
elif c == "2":
return False
else:
print("Enter Error!")
def main():
if not proof():
print("Check Failed!")
return
welcom()
if cmd():
f = open("file.py")
print(f.read())
return
mm = bytes_to_long(m)
assert pow(mm, e) != pow(mm, e, n)
sys.stdout.write("Please give me a padding: ")
padding = input().strip()
padding = int(sha256(padding.encode()).hexdigest(),16)
c = pow(mm+padding, e, n)
print("Your Ciphertext is: %s"%c)
if __name__ == '__main__':
main()
一：先說(shuō)一個(gè)阿三的例子：
（阿三不是侮辱稱(chēng)呼译株，是親切稱(chēng)呼）
由題目給的加密算法：
加密算法
轉(zhuǎn)化成數(shù)學(xué)公式如下：
c =（m + sha256（pad））** 3％n
注意：m**3>n(這里沒(méi)明白，為什么要>N)
以下就是阿三的重點(diǎn)：
阿三做了兩次填充，分別求出兩個(gè)密文（c1,c2）如下所示：
hash1 = int(sha256('2').hexdigest(), 16)
c1 = pow(m + hash1, e, n)
hash2 = int(sha256('1').hexdigest(), 16)
c2 = pow(m + hash2, e, n)
破解密碼算法如下：
1
消去共有項(xiàng)(h1 – h2)：
圖片.png
我相信大家看到這里就明白了吧娩践。本人做一個(gè)簡(jiǎn)單的解釋?zhuān)?/p>
1.由于e=3，冪指數(shù)比較低烹骨，且明文m和模數(shù)n都不變翻伺；
2.對(duì)c1,c2三次冪進(jìn)行展開(kāi)，消除同類(lèi)項(xiàng)展氓，得到一個(gè)二次冪的公式穆趴，
3.重點(diǎn)來(lái)了：使用二次冪求根公式，如下所示:
求根公式
這里不得不佩服阿三了遇汞，用一個(gè)簡(jiǎn)單的辦法來(lái)解決辦法未妹。
代碼如下：
mport hashlib
import gmpy2
from Crypto.Util.number import *
hash1 = int(hashlib.sha256('2').hexdigest(), 16)
hash2 = int(hashlib.sha256('1').hexdigest(), 16)
diff = hash1 - hash2
print "diff: ", diff
# M1 = M2 + diff
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941L
e = 3
c1 = 14550589053226237723784378782911157204367764723816957959635387925652898370034365455451983914571405062459535687617841302966938233065296973978472553109061974458935966754832788411876301179210585984208608247433383774246743661884093657109502619626436726032508763685599880808525861655167503719155953736308920858354069083437923495143680174206534169208623366776314544036377265501358254923029291010047210371394197963442022610746743020719292018028518885149189744832788117626194748311114409968846879212425054195323473068436359069318372735069308398135560733890706617536127579272964863500568572120716434126233695562326533941909353
c2 = 14550589053226237723784378782911157204367764723813789158271625147472004207734354619642445255036997940341703539883653916130592718879734436263217819317202435434496341973502556894834798718992952369685841347018901038478081710519253844078907000973324354805502890255414196801758171762906898874914776720897920729518384393581853690034053515213192846817920534901501370942556249012415259244063185938984570137371682805276444650716010228924732495062415330875872004691866847132147232457398743319930259327973290858489741376000333603734294893832124907092640953321640151851853501528390729805151850605432707293088635480863375398001441
b = 3*(hash1+hash2)
a = 3
c=(hash1**2+hash1*hash2+hash2**2)-(c1-c2)/(hash1-hash2)
det_pre=b**2-4*a*c
det = gmpy2.iroot(b**2 - 4*a*c, 2)
det = det=tuple(det)[0]
sol1 = (det - b)/(2*a)
print long_to_bytes(sol1)
#最終得到答案
小結(jié)：
- 阿三對(duì)數(shù)學(xué)和密碼學(xué)運(yùn)算掌握的比較熟簿废，能夠融匯貫通。
- 這道題原本的用意應(yīng)該不是這種解法络它。也許碰巧能用求根公式做族檬。
- 本人還是不明白，為什么要m^3>n化戳， 若有人知道這個(gè)簡(jiǎn)單問(wèn)題单料，請(qǐng)留言。
方法二：使用 sage
import hashlib
def chunk(input_data, size):
return [input_data[i:i+size] for i in range(0, len(input_data), size)]
def long_to_bytes(data):
data = int(data)
data = hex(data).rstrip('L').lstrip('0x')
if len(data) % 2 == 1:
data = '0' + data
return bytes(bytearray(int(c, 16) for c in chunk(data, 2)))
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
#monic()表示首系數(shù)為1的單項(xiàng)式
def franklin(n, pad1, pad2, c1, c2):
R.<X> = PolynomialRing(Zmod(n))
f1 = (X + pad1)^3 - c1
f2 = (X + pad2)^3 - c2
return -gcd(f1, f2).coefficients()[0]
#ciefficient():多項(xiàng)式的系數(shù)集合点楼，順序和集合的下標(biāo)相對(duì)應(yīng)
def main():
n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941
pad1 = int(hashlib.sha256("1").hexdigest(),16)
pad2 = int(hashlib.sha256("2").hexdigest(),16)
c1 = 14550589053226237723784378782911157204367764723813789158271625147472004207734354619642445255036997940341703539883653916130592718879734436263217819317202435434496341973502556894834798718992952369685841347018901038478081710519253844078907000973324354805502890255414196801758171762906898874914776720897920729518384393581853690034053515213192846817920534901501370942556249012415259244063185938984570137371682805276444650716010228924732495062415330875872004691866847132147232457398743319930259327973290858489741376000333603734294893832124907092640953321640151851853501528390729805151850605432707293088635480863375398001441
c2 = 14550589053226237723784378782911157204367764723816957959635387925652898370034365455451983914571405062459535687617841302966938233065296973978472553109061974458935966754832788411876301179210585984208608247433383774246743661884093657109502619626436726032508763685599880808525861655167503719155953736308920858354069083437923495143680174206534169208623366776314544036377265501358254923029291010047210371394197963442022610746743020719292018028518885149189744832788117626194748311114409968846879212425054195323473068436359069318372735069308398135560733890706617536127579272964863500568572120716434126233695562326533941909353
result = franklin(n, pad1, pad2, c1, c2)
print(long_to_bytes(result))
#我理解的意思是：
#1.消去多項(xiàng)式的最大公約數(shù)
#2.并把gcd返回的結(jié)果變成一個(gè)一次多項(xiàng)式 x+c
#3.取0次冪項(xiàng)（就是所說(shuō)的常數(shù)c）的相反數(shù),n-c為結(jié)果
#4.由于多項(xiàng)式模運(yùn)算扫尖，所以 以模n為界。
main()
解釋?zhuān)?/p>
R.<X> = PolynomialRing(Zmod(n))
Zmod(n):
1.指定模掠廓，定義界限為n的環(huán)换怖；Z表示整數(shù)
2.指定模是劃定這個(gè)環(huán)的界限:
3.就是有效的數(shù)字只有從0到n
4.其他的都通過(guò)與n取模來(lái)保證在0～n這個(gè)范圍內(nèi)
5：Zmod代表這是一個(gè)整數(shù)域中的n模環(huán)
R：只是一個(gè)指針，指向用polynomialring指定的那個(gè)環(huán)（可以使用任意字符）
PolynomialRing：這個(gè)就是說(shuō)建立多項(xiàng)式環(huán)
.<X>：指定一個(gè)變量的意思（可以用任意字符）
以下是一些做本次題目的相關(guān)知識(shí)：
Python strip()方法:
描述
Python strip() 方法用于移除字符串頭尾指定的字符（默認(rèn)為空格）蟀瞧。
語(yǔ)法
strip()方法語(yǔ)法：
'str.strip([chars]);'
參數(shù)
- chars -- 移除字符串頭尾指定的字符沉颂。
返回值
返回移除字符串頭尾指定的字符生成的新字符串。
實(shí)例
以下實(shí)例展示了strip()函數(shù)的使用方法：
str = "0000000 Runoob 0000000";
print str.strip( '0' ); # 去除首尾字符 0
str2 = " Runoob "; # 去除首尾空格
print str2.strip();
*********************************************************
以上實(shí)例輸出結(jié)果如下：
Runoob
Runoob
Python xrange() 函數(shù):
xrange()用法和讓完全按相同悦污，不同的就是生成不是一個(gè)數(shù)組铸屉，而是一個(gè)生成器。
xrange 語(yǔ)法：
xrange(stop)
xrange(start, stop[, step])
參數(shù)說(shuō)明：
參數(shù)說(shuō)明：
- start: 計(jì)數(shù)從 start 開(kāi)始切端。默認(rèn)是從 0 開(kāi)始彻坛。例如range（5）等價(jià) 于range（0， 5）;
- stop: 計(jì)數(shù)到 stop 結(jié)束帆赢，但不包括 stop小压。例如：range（0， 5） 是[0, 1, 2, 3, 4]沒(méi)有5
- step：步長(zhǎng)椰于，默認(rèn)為1。例如：range（0仪搔， 5） 等價(jià)于 range(0, 5, 1)
返回值
返回生成器瘾婿。
實(shí)例
以下實(shí)例展示了 xrange 的使用方法：
>>>xrange(8)
xrange(8)
>>> list(xrange(8))
[0, 1, 2, 3, 4, 5, 6, 7]
>>> range(8) # range 使用
[0, 1, 2, 3, 4, 5, 6, 7]
>>> xrange(3, 5)
xrange(3, 5)
>>> list(xrange(3,5))
[3, 4]
>>> range(3,5) # 使用 range
[3, 4]
>>> xrange(0,6,2)
xrange(0, 6, 2) # 步長(zhǎng)為 2
>>> list(xrange(0,6,2))
[0, 2, 4]
>>>
累加移位輸出：
for i in '-'+string.digits:
...: for j in '-'+string.digits:
...: for k in string.digits:
...: if((i!='-')and(j!='-')):
...: print(prepend+i+j+k)
...: elif((i=='-')and(j!='-')):
...: print(prepend+j+k)
...: if((j=='-')and(i=='-')):
...: print (prepend + k)
工作量證明算法:
（n1ctf 2018 解題前的驗(yàn)證算法）
from pwn import *
import hashlib
import string
from Crypto.Util.number import *
r = remote("47.75.39.249",'23333')
r.recvline()
str1 = r.recvline().strip()
print "condition: ", str1
prepend = str1[8:14]
sha_end = str1[len(str1)-15:len(str1)-10]
for i in string.letters + string.digits:
for j in string.letters + string.digits:
for k in string.letters + string.digits:
for l in string.letters + string.digits:
var = hashlib.sha256(prepend + i + j + k + l).hexdigest()[:5]
if var == sha_end:
print "gotit!"
print "happening: ", r.recvline()
r.recvline()
r.sendline(i + j + k + l)
print r.recvuntil("want?\n\n")
r.interactive()
r.sendline("1")
print r.recvall()
exit()
break
print "Failed!"
hash.digest()
返回摘要，作為二進(jìn)制數(shù)據(jù)字符串值
hash.hexdigest()
返回摘要烤咧，作為十六進(jìn)制數(shù)據(jù)字符串值
參考文獻(xiàn)：
工作量證明算法：http://blog.csdn.net/AAA123524457/article/details/52837510
mpz的一些用法：http://mcs.une.edu.au/doc/python3-gmpy2/mpz.html
sage網(wǎng)站：http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_ring_constructor.html
sage中文：https://www.lainme.com/doku.php/topic/sage/chapter_02/section_09
