i春秋新春赛Crypto记录

Crypto

Word count: 417Reading time: 2 min

 2020/02/24   Share

本菜依然很菜，只能做网上提供了脚本的题目。
但还是结合wp和自己的理解写点东西吧。

warm up

题目给了三个文件：

#challenge.py
from Crypto.Util.number import *
from encode import KEY

q=getPrime(1024)
p=getPrime(1024)
r=getPrime(1024)

s=getPrime(1500)

e1=125794
e2=42373

n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)

with open("enc","a")as f:
    f.write("c1: "+str(c1)+"\n")
    f.write("n1: "+str(n1)+"\n")
    f.write("n2: "+str(n2)+"\n")
    f.write("key_encode: "+str(key_encode)+"\n")

#encode.py
from flag import flag
import os


KEY = os.urandom(len(flag))

dec=int(flag.encode('hex'),16)


assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

#enc: 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

#enc
c1: 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
n1: 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2: 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
key_encode: 154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993

challenge.py关键代码

n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)

gcd求p、q、r，这个还是很容易想的
我的理解就是两个RSA题目求出s和Key，然后得出KEY的值，再去encode.py中求出flag：

assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

mask的值是确定的，且二进制值每一位都是1：

mask=0b11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

为了方便解释，我们令最初的

dec=int(flag.encode(‘hex’),16)

为dec0
而因为&1得本身
所以:

dec=(dec^dec<<200 )&mask
简化成dec=(dec^dec<<200)

python运算优先级:

左移200位，相当于最后增加两百位的0，而一开始assert len(bin(dec)[2:])==335，确定了dec0有335位，所以左移后变成535位，令dec<<200的结果为dec535 也就是下面（1）式求出来的dec有535位，最后200位是与最初的dec0的最后200位相等我们就知道了dec0的最后200位，设为declow200 因为左移200位，dec0与dec535异或，可以知道结果dec的高135位就是dec0的高135位，设为dechigh135 也就是dec中间200位没什么用所以就变成了提取值的问题了

#题目encode.py
assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

#求解
ec = key ^ enc
low200 = dec & ((1<<200)-1)
low135 = dec & ((1<<135)-1)
high135 = dec >> 200
high135 ^= low135
res = high135 << 200 | low200
print(long_to_bytes(res))

好的回到最关键的地方，怎么求challenge.py中的s和Key
gcd求出p,q,r

from Crypto.Util.number import *
p = math.gcd(n1,n2)
q = n1 // p
r = n2 // p

求出p,q，也知道了e1，接下来就是求逆元d，再求s
但是发现e1与phi1不互质，有公约数2，所以不能直接求

1
2
3

from Crypto.Util.number import *
phi1 = (p-1)*(q-1)
test=math.gcd(e1,phi1) #test=2

又想到了中国剩余定理(CRT)，但是改天半天网上的脚本还是算不对s
到此我就菜爆了
接下来给出Apeng的脚本
他是转换成Rabin问题求解

from Crypto.Util.number import *
print(dir())

c1 = 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
n1 = 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2 = 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
key_encode = 154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
enc = 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

p = math.gcd(n1,n2)
q = n1 // p
r = n2 // p
phi1 = (p-1)*(q-1)
e1=125794
e2=42373

e1 = e1 // 2
d1 = inverse(e1, phi1)

print(e1*d1 % phi1)

sp = pow(c1, (p+1)//4, p)
sq = pow(c1, (q+1)//4, q)
yp = inverse(p, q)
yq = -(yp * p - 1) // q
r1 = (yp*p*sq + yq*q*sp) % n1
r2 = n1 - r1
r3 = (yp*p*sq - yq*q*sp) %n1
r4 = n1 - r3

sc = [r1,r2,r3,r4]
ss = []
for i in sc:
    s = pow(i, d1, n1)
    n3 = p*q*s
    phi2 = (p-1)*(q-1)*(s-1)
    d2 = inverse(e2, phi2)
    key = pow(key_encode, d2, n3)
    dec = key ^ enc
    low200 = dec & ((1<<200)-1)
    low135 = dec & ((1<<135)-1)
    high135 = dec >> 200
    high135 ^= low135
    res = high135 << 200 | low200
    print(long_to_bytes(res))

报错：

NameError: name ‘bytes_to_long’ is not defined
导入这个模块：from Crypto.Util.number import *

LGG

vidar出的题，我觉得就是hgame密码的出题人，套一套用他们wp的POW的脚本
给了一个server.py，里面

def genDSA(self):
    q = number.getPrime(160)

    while True:
        X = random.getrandbits(1024)
        c = X % (q * 2)
        p = X - (c - 1)
        if number.isPrime(p) and p.bit_length()==1024:
            break

    e = (p - 1) // q
    h = 2
    g = pow(h, e, p)

    c = random.getrandbits(160)
    x = c % (q - 1) + 1
    y = pow(g, x, p)

已经明示DSA加密算法，接下来

def _is_valid_name(self, name):
        if not (0 < len(name) <= 20):
            raise ValueError("[*] name length inappropriate")

        for c in name:
            if c not in string.printable.encode():
                raise ValueError("[*] name is unprintable")

        if name == b'admin':
            raise ValueError("[*] name is equal to 'admin'")
...
if command == b'sign up':
    self.send(b'Give me your username')
    name = self.recv()
    (r, s) = self.sign_up(name)
    sig = name + r.to_bytes(20, 'big') + s.to_bytes(20, 'big')
    self.send(b'Here is your signature(hex)')
    self.send(sig.hex().upper().encode())

elif command == b'sign in':
    self.send(b'Give me your signature(hex)')
    hex_data = self.recv()
    data = binascii.unhexlify(hex_data)
    name = self.sign_in(data)
    self.send(str.encode(f"Welcome, {name.decode()}."))
    if name == b"admin":
        self.send(str.encode(f"The flag is {FLAG}."))

不给你用admin注册，但是要admin登录才给flag，也就是要让我们伪造签名
然后在网上找到一个脚本：https://xz.aliyun.com/t/3487#toc-7
基本是一样的思路= =，但是我觉得他的逻辑有点奇怪

而另外，我觉得主要的不同之处就是这道题

sig = name + r.to_bytes(20, ‘big’) + s.to_bytes(20, ‘big’)

只取20个字节
nc端口，可以得到p,q,g,y，输入sign up用admins注册，得到一串十六进制字符串

所以我改了一下鹏程杯那个脚本：

import string, binascii
import re
from hashlib import sha256
from hashlib import sha512

def s2h(s):
    return ''.join([hex(ord(c)).replace('0x', '') for c in s])

def h2i(s):
        #print(s)
        #print(type(s))
    return int(str(s),16)


def nonce(msg, num):
    n = 0
    msg=h2i(msg)
    num=h2i(num)
    for i in str(msg):
        i=int(i)**int(i)
        d=int(str(int(i)*3141592653)[-6:])
        n += num % d
    n = (num-n) % d
    #n=hex(n)
    return n


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 modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def sign(data):
    data = s2h(data)
    k = nonce(data,q)
    kinv = modinv(k, q)
    r = pow(g, k, p) % q
    h = sha512(data.encode("utf-8")).hexdigest()
    h = int(h,16)
    s = kinv * (h + r * priv) % q
    return (r, s)


def veryfy(data):
    h = sha512(data).hexdigest()
    h = int(h,16)


if __name__ == "__main__":
    p = 137013664977030299092518761023309129244979617778344173888358596526774388469732197061687345993886145178699887234503990569336984089812058495425666048486099274624016300046323564915395603195028938249366988881672482833027469510531562877274495741178721048556851730571434362558495712426184403156288538024678896955189
    q = 911387298423454764898459189010395207864556204687
    g = 66822843407472400101375116790419876599422430334988571844955373082792477181630931960307963456556522247655042977632942194358927060376192054040220539828415049509394888320946034659000858496078584352649487189233690715809973328503472495870399933736851422539529596441326171271626850910791146044119224178624602583236

    p = hex(p)
    q = hex(q)
    g = hex(g)
    hex_data='61646D696E734C8D0074862639D7FF179BFC042B70F1B139BDE42C1020EA86DD541530E49565D775CC4810947E90'
    data=binascii.unhexlify(hex_data)
    #print (data)
    (name, r1, s1) = (data[:-40], data[-40:-20], data[-20:])
    r1=int.from_bytes(r1, byteorder='big')
    s1=int.from_bytes(s1, byteorder='big')
    data=s2h("admins")
    k=nonce(data,q)
    #print (k)
    h = sha512(data.encode("utf-8")).hexdigest()
    h = int(h,16)
    priv1=((s1*k)%q-h)%q
    priv2=modinv(r1,q)
    priv=(priv1*priv2)%q
    #print (priv)
    (r,s)=sign("admins")
    # assert(r1==r)
    # assert(s1==s)
    #print (sign("admin"))
    name=b'61646D696E'
    sig = r.to_bytes(20, 'big') + s.to_bytes(20, 'big')
    sign1=(sig.hex().upper().encode())
    sign2=name+sign1
    print (sign2)

后面在看觉得应该是73、74行那个data有点问题（挖坑先）

此次比赛还让我真实地练了一下pwntools的使用
下面简单记录一下:（挖坑）

原脚本的一个报错：

TypeError: Unicode-objects must be encoded before hashing
将h = sha512(data).hexdigest()
改成h = sha512(data.encode(“utf-8”)).hexdigest()

EasyRSA

一个n两个c两个e，一看就知道是共模攻击，就一道签到题…

import gmpy2
from libnum import *
n = 27560959918385616419486273009594513460044316476337842585463553105701869531698366304637678008602799005181601310816935394003041930445509801196554897781529962616349442136039951911764620999116915741924245788988332766182305635804754798018489793066811741026902011980807157882639313892932653620491354630354060462594865874663773934670618930504925812833202047183166423043264815905853486053255310346030416687430724204177468176762512566055165798172418622268751968793997676391170773216291607752885987933866163158257336522567086228092863302685493888839866559622429685925525799985062044536032584132602747754107800116960090941957657
e1 = 464857
e2 = 190529
c1 = 21823306870841016169952481786862436752894840403702198056283357605213928505593301063582851595978932538906067287633295577036042158302374948726749348518563038266373826871950904733691046595387955703305846728530987885075910490362453202598654326947224392718573893241175123285569008519568745153449344966513636585290770127055273442962689462195231016899149101764299663284434805817339348868793709084130862028614587704503862805479792184019334567648078767418576316170976110991128933886639402771294997811025942544455255589081280244545901394681866421223066422484654301298662143648389546410087950190562132305368935595374543145047531
c2 = 9206260935066257829121388953665257330462733292786644374322218835580114859866206824679553444406457919107749074087554277542345820215439646770680403669560474462369400641865810922332023620699210211474208020801386285068698280364369889940167999918586298280468301097349599560130461998493342138792264005228209537462674085410740693861782834212336781821810115004115324470013999092462310414257990310781534056807393206155460371454836230410545171068506044174001172922614805135260670524852139187370335492876094059860576794839704978988507147972109411033377749446821374195721696073748745825273557964015532261000826958288349348269664
s0, s1, s2 = gmpy2.gcdext(e1, e2)
if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)
elif s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)
m = gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2, s2, n) % n

#print('[-]m is:', m)
print n2s(m) #flag{WuHanJiaYou!!!!!!}

Author：DGZ

原文链接：https://dgz-cyber.github.io/2020/02/24/i%E6%98%A5%E7%A7%8B%E6%96%B0%E6%98%A5%E8%B5%9BCrypto%E8%AE%B0%E5%BD%95/

发表日期：February 24th 2020, 10:18:30 am

更新日期：March 3rd 2020, 12:44:46 am

Next Post

i春秋新春赛pwn脚本
Previous Post

hgame2020 二发入魂及mt_rand()函数的记录

CATALOG

1. warm up
2. LGG
3. EasyRSA

