# discrete log

Writer : theoldmoon0602さん
[top](https://hackmd.io/ClxwWxDVSVC11Wrb-eGZIw)

Problem
---
People conclude discrete log is hard problem up to now.

# task.py
from Crypto.Util.number import getPrime, isPrime, getRandomRange

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    print(m)
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)

Output
---

# output.txt
10577926960839937947442162797370864980541285292536671603546595533193324977125572190720609448828374782284663027664894813711243894320697692129630847705557539
9947724104164898694903023872711663896409433873530762235716749042436185304062119886390357927264325412355223958396239523671881766361219889894069645084522127
[1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 8846898594122745402315346660588103073817097798204431437711034651813289442774837730820134043682352683522453026507938275715350738931942754620858572095894833, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 1945428232655195080994800854254286050005395375198086738205807646894444509288423023719076721279967584478447554044287458681202684205941300518455664909896770, 10354621433690291080863817499954203913680345790427806490217953854290390664868635054642758139322526900976315271173855068718334823237601765344488054950961045, 6450396411196778288237471377707156944771360666868782593043200729952706897922338702645020446957804453347793935766075212035314665465699530609262139446841794, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 8518396356987073160446226593505514680842064427706567536033369420610810908882528653260766790896766994789384117506763080763933744536854279875382388996716393, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 1451759830404925477558275270642407378934999719484439203872342683020817625642737205582986542429047217317435872276960585914530151288082605818539662897325059, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 3844728289551481985429176289449289604000304789858654366566902189290267618563940933188833996034764887276042750051165636121466021492112395693389564386737849, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 6075040072394386353700068186624559720007996691077752316710222658102597630426876503425968551345482454171942016710393973778088713964073715708282771166108340, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2319394889752437261970357119967349450311229179467143254112633795132104201041540419394974595546896804379819748025776699134680309317217660482163282654767536]

Solve
---
pに512bitの安全素数、q,rに2~p-1の乱数として、flagの1文字(m)ごとに $g^{r*m}\mod p$を計算し、csのリストに追加していったものを暗号文として出力している。
また、`output.txt`として与えられているのは p,q,cs の３つである。

csのそれぞれで変わるパラメータがmだけであることに注目した
また、flagの形式はCakeCTF{}であり、平文の範囲はAsciiの10進で33~126まであるから
平文のmとしてとりうる範囲の暗号文を作ればあとは対応させれば良さそう

Step1: $\;g^r\mod p$を作る
`CakeCTF{`まで平文が分かっていて、それぞれAsciiで
| `C` | `a` | `k` | `e` | `C` | `T` | `F` | `{` |
| - | - |- | - | - | - | - | - |
| 67 | 97 | 107 | 101 | 67 | 84 | 70 | 123 |

まず、`k=107`と`a=97`のから
$$g^{107r}*(g^{97r})^{-1}=g^{107r-97r}=g^{10r}\pmod p\quad (1)$$
同様に、`F=70`と`C=67`から$$g^{70r-67r}=g^{3r}\pmod p\quad (2)$$
同じく、`k=107`と`e=101`から$$g^{107r-101r}=g^{6r}\pmod p\quad (3)$$
(2)と(3)から$$g^{3r+6r}=g^{9r}\pmod p\quad (4)$$
(1)と(4)から$$g^{10r-9r}=g^r \pmod p$$
yoshi!

\[別解\]
$g^r \pmod p$はRSAの復号と同じ考え方(**オイラーの定理**)で計算できる
$g^{107*r} \pmod p$
の場合は、
法$\phi (p)=p-1$の107の逆元が計算できれば${(g^{107*r})}^{ \frac{1}{107}}=g^r$とできる

inv = pow(107,-1,p-1)
gr = pow(g**(107),inv,p)

Step2: 平文としてとり得る範囲全てのmに対して$\;{(g^r)}^m \mod p=g^{r*m}\mod p$を計算して各文字に対する暗号文の辞書を作る
Step3: csに対応する平文に置き換える

from Crypto.Util.number import long_to_bytes

p = 10577926960839937947442162797370864980541285292536671603546595533193324977125572190720609448828374782284663027664894813711243894320697692129630847705557539
q = 9947724104164898694903023872711663896409433873530762235716749042436185304062119886390357927264325412355223958396239523671881766361219889894069645084522127
cs = [1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 8846898594122745402315346660588103073817097798204431437711034651813289442774837730820134043682352683522453026507938275715350738931942754620858572095894833, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 1945428232655195080994800854254286050005395375198086738205807646894444509288423023719076721279967584478447554044287458681202684205941300518455664909896770, 10354621433690291080863817499954203913680345790427806490217953854290390664868635054642758139322526900976315271173855068718334823237601765344488054950961045, 6450396411196778288237471377707156944771360666868782593043200729952706897922338702645020446957804453347793935766075212035314665465699530609262139446841794, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 8518396356987073160446226593505514680842064427706567536033369420610810908882528653260766790896766994789384117506763080763933744536854279875382388996716393, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 1451759830404925477558275270642407378934999719484439203872342683020817625642737205582986542429047217317435872276960585914530151288082605818539662897325059, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 3844728289551481985429176289449289604000304789858654366566902189290267618563940933188833996034764887276042750051165636121466021492112395693389564386737849, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 6075040072394386353700068186624559720007996691077752316710222658102597630426876503425968551345482454171942016710393973778088713964073715708282771166108340, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2319394889752437261970357119967349450311229179467143254112633795132104201041540419394974595546896804379819748025776699134680309317217660482163282654767536]


# Step1 g^r mod p を求める
tmp1 = cs[2]*pow(cs[1],-1,p)    # g^107r * g^(-97r)  = g^10r
tmp2 = cs[6]*pow(cs[0],-1,p)    # g^70r  * g^(-67r)  = g^3r
tmp3 = cs[2]*pow(cs[3],-1,p)    # g^107r * g^(-101r) = g^6r
tmp4 = (tmp2*tmp3)%p            # g^3r   * g^6r      = g^9r
gr   = tmp1*pow(tmp4,-1,p)      # g^10r  * g^(-9r)   = g^r

# Step2 Asciiの範囲(33-126)に対して(g^r)^m mod pを計算
assert pow(gr,67,p)==cs[0]      # asciiの67(base10)は'C'

d = dict()
for i in range(33,127):
    d[pow(gr,i,p)] = chr(i)

# Step3 csに対応する平文に置き換える
ans = ""
for i in cs:
    ans += d.get(i)
    #print(d.get(i))

print(ans)

Flag
---
:tada: CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}

###### tags: `CakeCTF` `crypto`