Damgard-Jurik暗号の復号の練習

dj_solver.py

from sage.all import *
from Crypto.Util.number import long_to_bytes as l2b
import json

params = json.load(open("param.txt","r"))
s = params["s"]
n = params["n"]
c = params["c"]
g = params["g"]
p = 531457043239
q = 24388660549343689307668728357759111763660922989570087116087163747073216709529418907189891430183531024686147899385989241370687309994439728955541
l = lcm(p-1,q-1)
d = l

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

# Combination
def C(l,r):
    denom = 1
    numer = 1
    for i in xrange(1,r+1):
        denom *= i
        numer *= l-i+1
    return numer/denom

# Algorithm for decription of Damgard-Jurik CryptoSystem
def dj_dec_algo(a):
    b = L(a % n^2)
    for i in xrange(2,s+1):
        tmp = 0
        for j in xrange(1,i):
            tmp += C(b,j+1)*(n^j)
        b = L(a % n^(i+1)) - tmp
    return b % n^s

def main():
    jmd = dj_dec_algo(power_mod(c,d,n^(s+1)))
    jd = dj_dec_algo(power_mod(g,d,n^(s+1)))
    m =  jmd * inverse_mod(jd,n^s) % n^s
    print l2b(m)

if __name__ == "__main__":
    main()

param.txt

{
    "n":12961525424113842581457481341117729721726176698202598934475332596021163792495193687500962257794764397492324080568328705801930173334863551881104393545637299,
    "g":2132051839750573299754854507364380969444028499581423474830053011031379601163074792669440458939453573346412661307966491517309566840273475971253252815424138851541945813878339754880371934727997401840883756793174023026387912833787561873964774343104161427421558277429398462610380913199026766005036911561111911498015614446521644547923419768095811788791898552705927717854674901759443511325189376351325806917211560457327283300074902178726201347950069589670988213859630524059734789901571017367997352139514205408014889400527318603702898182503607166931422225113192039575979803468157633585201622512457745586383739179657894475772,
    "s":3,
    "c":16146846956417499078189378495360455759223869595378485457630764561369105704825747347552639327825348858161202688846334168331082417561328878910128831138772951255714265696309304528530025841643933748756877476450078970791315331759262515894580524581915667726800504296931313616859751122921688756817297843797340121021959810015729726300012075071651090158205135737206806416627610169333331691704947002581388291641532314716891417238670535879838292937496483821606837803344591931921999217676036196239569436244254894652087250116786992703898654314284929464910202202816397917119926061000276191503543076180026132619912576609446737065690
}

Damgard-Jurik暗号と呼ばれる暗号方式における復号の練習．公開鍵である(n,g(,s?))と暗号文cが分かっているという想定．
この暗号方式はPailliar暗号の一般化でもある．
ASIS CTF Final 2016のDam (crypto 277 pts)という問題で使われた．