pwnhub公开赛|Luukaka

题目放在下面

import random
from Crypto.Util.number import*

def Function(times,a,b):
    F = [2,a]
    for i in range(times):
        F.append( a * F[-1] - b * F[-2])
    return F

def Generate():
    a = 0b11011101110111110
    b = 0x11011101110
    s = (Function(77,a,b)[-1])
    while 1:
        if isPrime(s):
            break
        else:
            s = s >> 1
    tmp = (s << 64) + random.getrandbits(64)

    while 1:
        if isPrime(tmp):
            s = tmp
            break
        else:
            tmp = tmp + 1
    p = tmp
    q = getStrongPrime(1024)
    n = p * q
    return n

def Encrypt(m):
    n= Generate()
    g = random.randint(1,n**2)
    
    while 1:
        r = random.randrange(1,n)
        if GCD(r,n) == 1:
            break
    c =  (pow(g,m,n*n)*pow(r,n,n*n))%(n*n)
    return n , c , g

if __name__ == "__main__":
    flag = xxxxxxxxxxxxxx
    m = bytes_to_long(flag)
    n,c,g = Encrypt(m)
    print("n = " + str(n))
    print("g = " + str(g))
    print("c = " + str(c))

output

n = 14228073730190667444265758569232998545834341711432864414441434537856457554226009751489033431705491278975339077931622009743639467631071474363151300487078680100432725518596365988395929461561533250434031486424245896944629925135857622729999223390971276553928997508637911376545709237354833737994060265750787364825469605787468954601744025244062927831728713075259243916071854001703095748019042346899025896785151209455462423075169662092252456008356019267117214041106983803825784779879133738561202953888980952580302263891778856965344625783352907638953070740712616009213478262015624504889618788466893252102409611427088945902084609824939158090273141699828781599
g = 104756338318355948567384664103742452654286797799572772265848233334512623038814223410545840475708213491580933168492941525415723077772925906306730070567912467752229764629077391411738146979960676773739966985033493353135734679863468554065367379641641877776732166787383073606968314307988023048157536642389004806055502363198290047464507135522056378518722299068757453041609390692043233878813029502849305103895304519202811596850440711557164909395610847550061798126016783826231721060875732764619258276319683759960874598610474526487116193287935726659807081799695149604873036088612391197272153090414815760539467909235655538189612951075972603409435247362402276881345593351325034626085319241822974931255362490361433247117438845892276212349225050480473723922773661650238241659376681125743246319687880452040595990284620390242076959726572663250706701440702801135388505126093218792766996298711732747845811266552028107611595554772334895684283839272384369606543632542613172335294487221561323491737934377355876532240725521412046012357801914284413206938819420564131912564088387486730018108094449689965565218873981804619434009206386324135567769774069088701758230799594812616518042137489600048047478571983854027089251082355287707549749663822654965131297650047047655863594589307878048709000265824696160267631742318727023504
c = 110337660867664870668618596423399170421957516047679509225588623376743804308910177330738477934885576296064264107955132608068039716915229141255177656762910257465732348532323965821043865294553028096906547082618551373641823894294345439394320458729379584778338791447390149190354594056272453424922259417177887790371636260596466767307663828504719149380793176963386400546201890745560501746937761750771953027692686082999321908948997715677766808897936775024313229131624361695754073181908392043158729516103179521695533235615975097099246881718801578279171894214275303379728310998576306972004917364359907184627898803582606166064132907209594129554305783857639940803580780162589238990527574402229360311452329673309294811095686032780187382402401244208403608246186488287045631870185466768772070155917361936402870757098225660585142716834782054689740016959635568917565989361153748200711957665416078406041043067068946260735419003117885045170538814091969325447811589483805740159257095544507862038022099086715866062568327078082077714811272019367066364077835278254199402087714107154020099620284929159828186078676335901409411843708088949544768400190126243155520427016805835963333341089705359758522086506203013124445829394093909811080012839871046714948018821673486671778352056836826280481951815377888832291151086485700501159

前置知识

同态加密

精髓

即先计算后解密可等价于先解密后计算。

同态加密的思想起源于私密同态，代数同态和算术同态是私密同态的子集。

R 和 S 是域，称加密函数 E：R→S 为：

加法同态，如果存在有效算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，并且不泄漏 x 和 y。

乘法同态，如果存在有效算法 ，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，并且不泄漏 x 和 y。

混合乘法同态，如果存在有效算法 ，E(x×y)=E(x) y 或者 xy=D(E(x) y)成立，并且不泄漏 x。

减法同态，如果存在有效算法○- ，E(x-y)=E(x)○- E(y)或者 x-y=D(E(x)○- E(y))成立，并且不泄漏 x 和 y，则称 E 为减法同态。

除法同态，如果存在有效算法○/ ，E(x/y)=E(x)○/ E(y)或者 x/y=D(E(x)○/ E(y))成立，并且不泄漏 x 和 y，则称 E 为除法同态。

代数同态，如果 E 既是加法同态又是乘法同态。算术同态，如果 E 同时为加法同态、减法同态、乘法同态和除法同态。

lucas序列

参考链接

https://blog.csdn.net/YangHao5/article/details/90022768

Paillier加解密

key的产生

1、选取两个大素数p、q

2、计算n=pq,λ=lcm(p−1,q−1)

3.在

群上选择一个大数，即产生随机数g

4、确保逆元存在，用来计算μ=(L(g^λmodn^2))^(−1)modn,函数L定义为

加密

解密

其中公钥为n,g，私钥为λ,μ

上述内容由wiki得

本题解题思路

1、coppersmith攻击

2、常规解密

其中task.py里给出了a和b,其实我们可以得到s

然后coppersmith可以得到p

89993381987137506011679842153708782600347540345541532955617801526876380951385052938276977563645108845230982081550367480695643488174519956646559392653544017312457803311443093956372962621108795325336827097398138660534143621582730017517058772398513495619577181034288859950414446489334860611610502414840411291040940750561767344688920500749873731
然后一路解下去就没有什么问题了