N1CTF 2018：RSA_Padding

作者: Black_Sun | 来源:发表于2018-03-14 23:37 被阅读898次

题目如下：

首先：

验证工作
如何解，请看下面工作量证明算法
接下来：

图片.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()

一：先说一个阿三的例子：

（阿三不是侮辱称呼，是亲切称呼）

由题目给的加密算法：

加密算法

转化成数学公式如下：

c =（m + sha256（pad））** 3％n

注意：m**3>n(这里没明白，为什么要>N)

以下就是阿三的重点：

阿三做了两次填充，分别求出两个密文（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)

破解密码算法如下：

消去共有项(h1 – h2)：

图片.png

我相信大家看到这里就明白了吧。本人做一个简单的解释：

1.由于e=3，幂指数比较低，且明文m和模数n都不变；
2.对c1,c2三次幂进行展开，消除同类项，得到一个二次幂的公式，
3.重点来了：使用二次幂求根公式，如下所示:

求根公式

这里不得不佩服阿三了，用一个简单的办法来解决办法。
代码如下：

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)
#最终得到答案

小结：

阿三对数学和密码学运算掌握的比较熟，能够融汇贯通。
这道题原本的用意应该不是这种解法。也许碰巧能用求根公式做。
本人还是不明白，为什么要m^3>n，若有人知道这个简单问题，请留言。

方法二：使用 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()表示首系数为1的单项式
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():多项式的系数集合，顺序和集合的下标相对应
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.消去多项式的最大公约数
#2.并把gcd返回的结果变成一个一次多项式 x+c
#3.取0次幂项（就是所说的常数c）的相反数,n-c为结果
#4.由于多项式模运算，所以 以模n为界。
main()

解释：

R.<X> = PolynomialRing(Zmod(n))
Zmod(n):
1.指定模，定义界限为n的环；Z表示整数
2.指定模是划定这个环的界限:
3.就是有效的数字只有从0到n
4.其他的都通过与n取模来保证在0～n这个范围内
5：Zmod代表这是一个整数域中的n模环
R：只是一个指针，指向用polynomialring指定的那个环（可以使用任意字符）
PolynomialRing：这个就是说建立多项式环
.<X>：指定一个变量的意思（可以用任意字符）

以下是一些做本次题目的相关知识：

Python strip()方法:

描述

Python strip() 方法用于移除字符串头尾指定的字符（默认为空格）。

语法

strip()方法语法：

'str.strip([chars]);'

参数

chars -- 移除字符串头尾指定的字符。

返回值

返回移除字符串头尾指定的字符生成的新字符串。

实例

以下实例展示了strip()函数的使用方法：

str = "0000000     Runoob  0000000"; 
print str.strip( '0' );  # 去除首尾字符 0
str2 = "   Runoob      ";   # 去除首尾空格
print str2.strip();
*********************************************************
以上实例输出结果如下：
    Runoob  
Runoob

Python xrange() 函数:

xrange()用法和让完全按相同，不同的就是生成不是一个数组，而是一个生成器。

xrange 语法：

xrange(stop)
xrange(start, stop[, step])

参数说明：

start: 计数从 start 开始。默认是从 0 开始。例如range（5）等价于range（0， 5）;
stop: 计数到 stop 结束，但不包括 stop。例如：range（0， 5）是[0, 1, 2, 3, 4]没有5
step：步长，默认为1。例如：range（0， 5）等价于 range(0, 5, 1)

返回值

返回生成器。

实例

以下实例展示了 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)              # 步长为 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 解题前的验证算法）

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() 
返回摘要，作为二进制数据字符串值
hash.hexdigest() 
返回摘要，作为十六进制数据字符串值

参考文献：
工作量证明算法：http://blog.csdn.net/AAA123524457/article/details/52837510
mpz的一些用法：http://mcs.une.edu.au/doc/python3-gmpy2/mpz.html
sage网站：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

N1CTF 2018：RSA_Padding

题目如下：

首先：

一：先说一个阿三的例子：

c =（m + sha256（pad））** 3％n

以下就是阿三的重点：

破解密码算法如下：

小结：

方法二：使用 sage

以下是一些做本次题目的相关知识：

Python strip()方法:

描述

语法

参数

返回值

实例

Python xrange() 函数:

xrange 语法：

参数说明：

返回值

实例

工作量证明算法:

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

信息安全

黑客