安恒四月春季战

badmonkey 2020年04月25日 576次浏览

安恒四月春季战

not_RSA

emmm，一开始没有看出来是个啥玩意。。后来Google了一下，发现是个Paillier cryptosystem，其实之前是看到过这个加密系统的，但是没有深入了解。这次正好记录一下吧。

在维基上以可看到，该系统具有累加性，知道公钥的情况下，已知m1，m2的加密结果，可以算出m1+m2的加密结果(虽然和这题没啥关系，但是是一个很有意思的性质

加密流程：

Key generation

  • 选择两个大素数p,q使得$\gcd(pq,(p-1)(q-1)) =1$
  • $n=pq \quad and \quad \lambda =lcm(p-1,q-1)$
  • 随机选择一个$g$使得$g \in Z_{n^2}^*$
  • $\mu = (L(g^\lambda\mod n^2))^{-1}\mod n$，其中$L(x) = \frac{x-1}{n}$

公钥为$(n,g)$，私钥为$(\lambda,\mu)$

加密流程:

encryption

  • 随机选择$r$使得$r\in Z_n^ \quad and \quad \gcd(r,n) = 1$
  • 密文为$c=g^m r^n \mod n^2 $

解密流程:

decryption

  • $m=L(c^\lambda\mod n^2) \cdot \mu \mod n$

不过该题不是标准的Paillier cryptosystem，而是阉割版。Wiki上也写了。

  • $g=n+1$
  • $\lambda = \phi(n)$
  • $\mu = \phi(n)^{-1} \mod n$

此题给出了g，而且n用yafu很容易算出来。（factordb是算不出来的

于是可以得到私钥信息，按照流程解密即可，题面信息：

from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from secret import flag,p,q
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)

print "c=%d"%(c)
print "n=%d"%(n)

'''
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
'''

解题脚本：

#! /bin/bash/env python2
from gmpy2 import *
from Crypto.Util.number import *
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549

phi = (p-1)*(q-1)
lam = phi
miu = invert(phi,n)

def L(x):
    return (x-1)//n

def decrypt(c):
    x = powmod(c,lam,n*n)
    m = L(x)
    return (m*miu)%n


flag = decrypt(c)

print long_to_bytes(flag)
# flag{5785203dbe6e8fd8bdbab860f5718155}

ComplexEncode

题面信息：

from Crypto.Util.number import *
from flag import FLAG,false_flag
import gmpy2
import random
import hashlib
import base64

def rsaEncode(msg):
    f=open("out","a")
    while True:
        ran=random.randint(3, 12)
        if isPrime(ran):
            break
    e=ran*getPrime(30)
    p = getPrime(1024)
    q = getPrime(1024)
    while (not gmpy2.gcd((p-1)*(q-1),e)==ran or p*q<pow(msg,ran)):
        p = getPrime(1024)
        q = getPrime(1024)
    n=p*q
    assert(pow(msg,ran)<n)
    print("rsaEncode_init_finish!")
    dsaEncode(p)
    f.write("rsaEncode n:"+hex(n)+"\n")
    f.write("rsaEncode e:"+hex(e)+"\n")
    c=pow(msg,e,n)
    f.write("rsaEncode flag is:"+hex(c)+"\n")
    f.close()

def rsaEncode2(m):
    m=int.from_bytes(m.encode(),'big')
    f=open("out","w")
    while True:
        ran=random.randint(20, 50)
        if isPrime(ran):
            break
    e=ran*getPrime(30)
    p = getPrime(1024)
    q = gmpy2.next_prime(p)
    while (not gmpy2.gcd((p-1)*(q-1),e)==ran or p*q>pow(m,ran)):
        p = getPrime(1024)
        q = gmpy2.next_prime(p)
    n=p*q
    assert(pow(m,ran)>n)
    c=pow(m,e,n)
    f.write("n2:"+hex(n)+"\n")
    f.write("e2:"+hex(e)+"\n")
    f.write("rsaEncode2 re is:"+hex(c)+"\n")
    f.close()
    print("rsaEncode2_finish!")
    return pow(m,ran,n)

def dsaEncode(p):
    key=genkey(p)
    (r,s,k,q)=sign(rsaEncode2(false_flag),key)
    sig= r.to_bytes(205, 'big') + s.to_bytes(205, 'big') + k.to_bytes(205, 'big')+ q.to_bytes(205, 'big')
    f=open("out","a")
    f.write("dsaEncode :"+base64.b64encode(sig).decode()+"\n")
    f.close()

def genkey(x):
    # DSA
    N=1024
    L=2048-N-1
    while True:
        q = getPrime(N)
        if q-1>x:
            break
    assert(q-1>x)
    while True:
        t = random.getrandbits(L)
        p = (t * 2*q + 1)
        if isPrime(p):
            break
    e = (p-1) // q
    g = pow(2, e, p)
    y = pow(g, x, p)
    print("genkey_finish!")
    return {'y':y, 'g':g, 'p':p, 'q':q, 'x':x}

def sign(m, key):
    g, p, q, x = key['g'], key['p'], key['q'], key['x']
    k = random.randint(1, q-1)
    Hm = int.from_bytes(hashlib.md5(str(m).encode('utf-8')).hexdigest().encode(), 'big')
    r = pow(g, k, p) % q
    s = (inverse(k, q) * (Hm + x*r)) % q
    return (r, s, k, q)

if __name__ == "__main__":
    msg=int.from_bytes(FLAG.encode(),'big')
    rsaEncode(msg)

题目附件信息:

n2:0x431a834246a5969d460cee6b7db01ec4e05daffd60d6674fd1cf3ab96544ad788df5ef729eba08fce3d6c237b47b7cbda093fb414672eea6a58bd902c7e73844a85b2626e3f17a2c2b6c6521288925792bfa2a338cf1d2128d771b55bac2a2cc85f95dd68b4463661813c7ed268c1ca203c74b513edf749799acbfd70b656976f81d124c0385f4dfe549185a4853ace927db615c1ce95b8230a504dbdc6db1ff639e9700e6f074432493b6bf1aa349a9cf66a7116a6095803718a5b78d541b7fbf643bed0bbde5a9370f54a457feef2fde1db15012c337385d011c4a601fe092a0b0a503b65efb1d2c70de6883a504d04292e4216e5c586e0df85b00732460f5
e2:0x57e6b0c63
rsaEncode2 re is:0x174e74a04d09ee859030c9fa292c266f9de06bf833dcffc5d24a4382251620cac743cf2d500428d5784fc271e610965547675db2716a9ab277395fc565a2d8520b21d4384a525beda292c276b4477852255c910b0dd08374e68e421b137d90c6c8ca98e219a73231eb285707fff221e57a005113ec16ef61bde87bebd69da1d09cccda411242ba7607a470b31e54e79603eb2c568825a7534df24d0e411fa60d96925f3f2cc63e3ab60f1fe51be80009aba3fdfe947365e578f04fd04a1f9e4afb5fc7ccc1ee831622917386c0d7ae00e6f3f4abd818f6e76d9d173a2e53357496441ae140284c8a6cc3aa22232f1a58fc101427236f2c2afc2277470eb83116
dsaEncode :AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACR4uuC531illQ9yIEW1Ki22kYtZNrX77elRFDZr8EKcnrkZC+yyMxlxFNsCrFqEPhGzAPXS++Aa248WMv1uZDNIzi84jiMw7ZWS82OKEwzy0ozV7lEa7deI+QoVdl49kXx3ZVaR2/TrXrfr3dkiBQyORp/DPsSQdkdLoCmtgNycQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAmkIjVBdkWLaqnSz0OdPi69RsjMwT1wVxq81vfDFnOO+JYKfG0OiAZEeJoSeParez6jBH0+RLVc4f6xOFgZcDYopkzR8ZNYlJR78oWmi/0cuxt4nYTTVirtUux3JrT75YQ/+bWmhswBMHQeIAttvqoZp/YZPOmHZdDkl7arrdZ5UAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEt+f1ID5QKI6NEqnVMMputnxfuIs4hCKZbPCEeV6uGoLJSbKaxBlzaO37bTzINBAxCcKQfCsV4ZwZFpTmozZ/dSdoKnIq/tcPh++80pUAjSjVI/rVInJi4CKgaeaf/8MX8ajCImkLJt6N4pA109eZ6TVJDFnbSRRY9P5i5iF2XwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACh5RoGbxvmvqT2pj93NhFj5UruyVjoxCkyw5kD2qEVCfKXZT1ysK9F5A2MJuU1qLKiJ76ATUVid1dtanCzd8XzkzfdY3nEtxqJ4CEJTSnIuthBz4ETBd8+v2+Oc4nTaimIdhQrEtI5M2z9+tq+uQ/qaXbg735CQiU7jjyALgOCoQ==
rsaEncode n:0x769bf99a95e9f446788300bfc679b04f26498d26ce1f1384ef22a4bc0606d2fdcf4af86b8e9b26003f561532613a8b7bcb09c0009aefc09c5297f53342b9fe111562c0789dfa91ff4def12c7cb551828079418e1244387f392d6f420c04eb8b99278f5dacb6042828dae19c1f6638d46f9601aceee1511bf600ef548db15ea6ce1ae975cd08236fdac7d457ac9fa203c8f7914702c78dc3ef24fa50c32208225096f5af761f9e4c581dfca7dbc2a4062d59196578e0213a8d1d8a05bfe398a3c8c195b3997fb01b930e2c925732ef78fdd39b4e4681ab3fea4d2c4f1a3b935df5d494817e2c8eef72e3f22f1ef80c3455add7206baf92495ae59adaa7f1bfd25
rsaEncode e:0x12a316381
rsaEncode flag is:0xa97f8fd2cbf4aa1cae331dc5261c93a8da3c0a4aadd33cf204cdb2e38e3afdd16aed1a23cd911f96ddc7152b14120949235c0f1849999c5eae06932900f0ccb7c19fb3854623dc0bbc9b9b1fe640075d1db0be91f0e45776b959d008edd17cf41c24d711a5c767d10a630eec8d96baf2668a358c3cbe4533e410667748d73725c04113e9c7d4f19d520aab6b3241a96feb54632a6f816efdc3a2d7c28604a25ce9fd3dc1d0210e0c70132618125bf8eae1f73fa48699fb7cffe5721b5b7fc8511d6cec4ecef1a8bca0d8fe29b0856b3648feac3f1020650063c40be606d9faf0004517dfb202dfb9c664a887f366119ef2efcbf84813f9a4ad54e9ad05e20f0

看到很长的代码，以为会是到很难的paper题。没想到是一道套娃题，不过涉及的知识点，还是挺多的(出题人要是再多套几层，估计会被打死吧。

主要逻辑是一个rsa加密，rsa的p被当作参数用来传进genkey，然后用dsa签名搞一下，不过出题人给出了签名的所有信息（除了x，也就是rsa的p）的base64编码。于是可以还原得到dsa 中的r,s,k,q 由于
$$
s=k^{-1}\cdot(Hm+x\cdot r)\mod q
$$
其中的s，k，r，q已知，Hm是rsaEncode2 的结果的md5值，也是可以算出来的。所以同余式中只有x，不知道，可以变换一下得到
$$
(s\cdot k -Hm)\cdot r^{-1} \mod q = x \mod q
$$
其中x<q-1,也就是说x，就是等式右边的结果

那么接下来就是算Hm了。首先算rsaEncode2 的结果，n2很容易分解，不过需要注意的是，$gcd(e2,phi2)=ran2 \quad ran2 = 41$，于是不能直接算$(m2)^{ran2} \ mod n2$。需要变化一下，变换如下
$$
e2 = ran2 \cdot x2
$$

$$
ran2 = e2\cdot x2^{-1}
$$

$$
(m2)^{e2\cdot x2^{-1}} \mod n2 = (m2)^{ran2} \mod n2
$$
于是可以得到rsaEncode2 的结果，然后就是一波流。写好脚本跑一下，就出来了。exp如下：

from gmpy2 import *
from base64 import b64decode
from hashlib import md5
from Crypto.Util.number import long_to_bytes, bytes_to_long

n = 0x769bf99a95e9f446788300bfc679b04f26498d26ce1f1384ef22a4bc0606d2fdcf4af86b8e9b26003f561532613a8b7bcb09c0009aefc09c5297f53342b9fe111562c0789dfa91ff4def12c7cb551828079418e1244387f392d6f420c04eb8b99278f5dacb6042828dae19c1f6638d46f9601aceee1511bf600ef548db15ea6ce1ae975cd08236fdac7d457ac9fa203c8f7914702c78dc3ef24fa50c32208225096f5af761f9e4c581dfca7dbc2a4062d59196578e0213a8d1d8a05bfe398a3c8c195b3997fb01b930e2c925732ef78fdd39b4e4681ab3fea4d2c4f1a3b935df5d494817e2c8eef72e3f22f1ef80c3455add7206baf92495ae59adaa7f1bfd25
e = 0x12a316381
c = 0xa97f8fd2cbf4aa1cae331dc5261c93a8da3c0a4aadd33cf204cdb2e38e3afdd16aed1a23cd911f96ddc7152b14120949235c0f1849999c5eae06932900f0ccb7c19fb3854623dc0bbc9b9b1fe640075d1db0be91f0e45776b959d008edd17cf41c24d711a5c767d10a630eec8d96baf2668a358c3cbe4533e410667748d73725c04113e9c7d4f19d520aab6b3241a96feb54632a6f816efdc3a2d7c28604a25ce9fd3dc1d0210e0c70132618125bf8eae1f73fa48699fb7cffe5721b5b7fc8511d6cec4ecef1a8bca0d8fe29b0856b3648feac3f1020650063c40be606d9faf0004517dfb202dfb9c664a887f366119ef2efcbf84813f9a4ad54e9ad05e20f0

n2 = 8471040347180588439431756063803418012156520263169094341319795495789676296157791602584828441035800122980586220640515219679498414176176191802659583932599225366219907537999414023995947652164844830780211307318233010857464278373538833912283531198488479960126436983808457379189532193303642762797320117839616980944223783271337969984253461166869585991030060030131230830527861814305985813300265161470771092850585136444032041203294581336010732656284788520182213884303958771619162366594389832144604238730274900312074631398625925678261167539016451268707303375139482592259256907872617855839967205583557823137333491096372266688757
e2 = 23595781219
c2 = 0x174e74a04d09ee859030c9fa292c266f9de06bf833dcffc5d24a4382251620cac743cf2d500428d5784fc271e610965547675db2716a9ab277395fc565a2d8520b21d4384a525beda292c276b4477852255c910b0dd08374e68e421b137d90c6c8ca98e219a73231eb285707fff221e57a005113ec16ef61bde87bebd69da1d09cccda411242ba7607a470b31e54e79603eb2c568825a7534df24d0e411fa60d96925f3f2cc63e3ab60f1fe51be80009aba3fdfe947365e578f04fd04a1f9e4afb5fc7ccc1ee831622917386c0d7ae00e6f3f4abd818f6e76d9d173a2e53357496441ae140284c8a6cc3aa22232f1a58fc101427236f2c2afc2277470eb83116
# p 是dsa encode 部分算
q2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186724103
p2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186723619
phi2 = (p2 - 1) * (q2 - 1)
ran2 = gcd(phi2, e2)
# ran2 = 41
# e2 = ran2*x2 gcd(x2,phi2)=1
inv_x2 = invert(e2 // ran2, phi2)
# inv_x2 = 7009900126152370967434113527543712252506070314516976273229109461958446019343630403936205889263932137362824877808019152972250787864647348088253742288780061585418965682676219052623386021425976739947656816356199324609311718987340519854222787557120824113959668427851289623323261079352922751724164902366076417526544952027720357754589297753097503413281990459097985581838990358666439190612104658506622092228502369965922337807538461600247546074944800924201334592978342525911135025077671767611075425260380724796650817133123038926753601485388930095213549268473925186434831073392577443562038926251230122649106116078690345361087
# m2^ran2%n2 = c2^inv_x2 % n2
rsa2 = int(powmod(c2, inv_x2, n2))
dsa = 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACR4uuC531illQ9yIEW1Ki22kYtZNrX77elRFDZr8EKcnrkZC+yyMxlxFNsCrFqEPhGzAPXS++Aa248WMv1uZDNIzi84jiMw7ZWS82OKEwzy0ozV7lEa7deI+QoVdl49kXx3ZVaR2/TrXrfr3dkiBQyORp/DPsSQdkdLoCmtgNycQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAmkIjVBdkWLaqnSz0OdPi69RsjMwT1wVxq81vfDFnOO+JYKfG0OiAZEeJoSeParez6jBH0+RLVc4f6xOFgZcDYopkzR8ZNYlJR78oWmi/0cuxt4nYTTVirtUux3JrT75YQ/+bWmhswBMHQeIAttvqoZp/YZPOmHZdDkl7arrdZ5UAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEt+f1ID5QKI6NEqnVMMputnxfuIs4hCKZbPCEeV6uGoLJSbKaxBlzaO37bTzINBAxCcKQfCsV4ZwZFpTmozZ/dSdoKnIq/tcPh++80pUAjSjVI/rVInJi4CKgaeaf/8MX8ajCImkLJt6N4pA109eZ6TVJDFnbSRRY9P5i5iF2XwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACh5RoGbxvmvqT2pj93NhFj5UruyVjoxCkyw5kD2qEVCfKXZT1ysK9F5A2MJuU1qLKiJ76ATUVid1dtanCzd8XzkzfdY3nEtxqJ4CEJTSnIuthBz4ETBd8+v2+Oc4nTaimIdhQrEtI5M2z9+tq+uQ/qaXbg735CQiU7jjyALgOCoQ=='
dsadecode = b64decode(dsa)
_r = int.from_bytes(dsadecode[:205], 'big')
_s = int.from_bytes(dsadecode[205:410], 'big')
_k = int.from_bytes(dsadecode[410:615], 'big')
_q = int.from_bytes(dsadecode[615:], 'big')
Hm = int.from_bytes(md5(str(rsa2).encode('utf-8')).hexdigest().encode(), 'big')
inv_r = invert(_r, _q)
p = (inv_r * (_s * _k - Hm)) % _q
q = n // p
assert p * q == n

phi = (p - 1) * (q - 1)

ran = gcd(e, phi)
# ran = 5
# e = ran*x gcd(x,phi) == 1
inv_x = invert(e // ran, phi)
m5 = powmod(c, inv_x, n)
flag = iroot(m5, 5)[0]
print(long_to_bytes(flag))
# flag{2a4d55342b46289d1f624d3083c5e2de}
上一篇： 2020网鼎杯青龙组