CTFにおけるCrypto入門とまとめの1つです。

• DLP: 離散対数問題
• 離散対数問題の効率的な解法
  • Pohlig–Hellman法
• DLPの困難性を利用した暗号
  • Deffie-Hellman 鍵共有
  • ElGamal暗号
  • ElGamal署名
  • Schnorr（シュノア）署名
  • DSA: Digital Signature Algorithm

DLP: 離散対数問題

• https://tex2e.github.io/blog/crypto/DLP
• 離散対数問題 y=g^x mod p でy,g,pが既知で、xを計算するのが難しいという問題
• CDH仮定
  • DH問題, DDH: 後述するDH鍵共有で現れる問題、g,p,g^a mod p, g^b mod pが与えられたときにg^ab mod pを求めよという問題
  • DH問題が難しいという過程をCDH仮定と呼ぶ
    • DLPが解けるならばDH問題も解ける（逆はわからない）
  • DDH仮定が成立しない場合 https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
    • 乗法群: g^aとg^bとg^abがあるとき、a,b,abの偶奇性をルジャンドル記号で判別できる
      • https://gmo-cybersecurity.com/blog/ierae-ctf-2025-writeup-crypto/
    • 楕円曲線上
• DLPは、どの上で考えるかで色々ある。どういう条件だと使えるのかはあまりよく分かっていないし、(Fp)*と同型だから使える?ちゃんと理解してない
  • FFDLP: Finit Field DLP, 有限体Fp上でDLPを考えたもの。y=g^x mod pのこと。本稿では主にFFDLPを対象とする
  • ECDLP: 楕円曲線上でDLPを考えたもの
  • 多項式環上のDLP: InCTF 2020 - DLPoly https://crypto-writeup-public.hatenablog.com/entry/InCTF_2020_%257C_DLPoly
  • 行列の離散対数問題を解く -> 別稿で解説
  • 対称群のDLP redpwnCTF 2021 scrambled-elgs https://blog.y011d4.com/20210713-redpwnctf-writeup#scrambled-elgs
• cado-nfsを使うと256bitsの離散対数問題は解けてしまう
  • https://zenn.dev/koba_e964/articles/263643a1fc76c3
• dlogと表記されることも（対数ログ）
• DLPが効率的に計算できる状況ならば、総積にlogを取って総和に変換できる
  • https://blog.whale-tw.com/2025/10/19/qnqsec-ctf-2025/#Republic-of-Geese では総和に変換してLLLしてる
  • 対数を取るときの基数は適当でいいが上の解説だと2を使ってる discrete_log(Zmod(p)(iter), Zmod(p)(2))

離散対数問題の効率的な解法

• Baby-step Giant-step法 O(sqrt(p))
• Pollard's rho法 O(sqrt(p))
  • 実装例 https://writeups.thebusfactoris1.online/posts/2025-09-05-field-trip-writeup
• Pollard's kangaroo algorithm / Pollard's Lambda法: 離散対数の探索範囲が限定されている場合に特に効率が良いアルゴリズム
  • sagemath secret_A = discrete_log_lambda(A, G, bounds=(1000000, 100000000))
  • SECPK1向けソルバ https://github.com/JeanLucPons/Kangaroo
    • https://github.com/Warriii/CTF-Writeups/blob/main/deadsec25/crypto_bullmad.md
    • nonceの差を全探索して全部でKangaroo法を適用する計算重すぎて手元だと遅かったけど、Googe Collab使うとマシンパワー強くて速かったという情報がある
• Pohlig–Hellman法
• 指数計算法（Index Calculus Algorithm）

Pohlig–Hellman法

• 位数の約数がsmoothであるときに離散対数問題が効率的に解けるという問題
  • mod pであればp-1が位数なので、p-1がsmoothであればいい
  • 位数がp²-1であれば、p²-1がsmoothであればいい
    • 満たすpをランダムで根性探索するコード https://github.com/y011d4/my-ctf-challenges/blob/main/2023-SECCONCTF-Final/crypto/dlp-4.0/solution/find_p.sage
  • これ、点の位数なので注意（g^x mod pの場合は点の位数=全体の位数かもなので問題ないかもだけど、楕円曲線の時とかは注意）
• 離散対数問題 y=g^x mod p に対して、x部分の上限がより小さくなった問題に分割して計算する方法
• 計算方法
  1. (p-1)を因数分解する。q1 * q2 * ... qk になったとする
     • q1,q2,...,qkは互いに素である必要がある。よって、素因数分解した上で各素因数の累乗についてqiとしてまとめていくことになる
  2. 各qiについて、yi = y ^ (p-1/qi), gi = g^(p-1/qi)と定義して yi = gi^ai mod pで0≦ai＜qiとして離散対数問題を解きaiを求める
     • p-1の因数分解の結果がsmoothな（最大値が小さい）ときにこの小問題が解けてPohling-Hellman法が適用可能になる
     • なぜこうなるかについては、x = ai + bi * qiと定義した後にy ^ (p-1/qi)を色々計算して、逐次定義を付けるとyi = gi^aiが得られる
  3. この時得られたaiの値はx = ai mod qiを満たすので、CRTを適用することでxが得られる
• ちなみにsageのdiscrete_logはpohlig-hellman + BSGS
  • sageのdiscrete_logは素因数分解できた全部でbsgsやろうとするから、最後の一素因数についてはやらなくていいみたいな場合は手動でやる

DLPの困難性を利用した暗号

Deffie-Hellman 鍵共有

• Deffie-Hellman 鍵共有: 2者間で秘密a,bを交換することで秘密鍵g^abを秘密裏に共有できるアルゴリズム
• 手順
  1. 整数 g,p を事前に両者で決める（公開して良い）
  2. Aさんが秘密aを、Bさんが秘密bを持っているとする
  3. それぞれ、KA = g^a mod p, KB = g^b mod p を計算して相手に渡す （つまり、g, p, KA, KBは公開情報で、aはAさんのみ、bはBさんのみ知っている状態）
  4. Aさんは KB^a, BさんはKA^bをすることで、互いにg^abを取得することができる。これは公開情報のみで作るのは困難である
• g, pの条件
  1. pは1024ビット以上の素数で、p-1の約数の中にpに近いサイズの素数qがある
     • ベストは(p-1)/2が素数
  2. gはi=1, ..., q-1に対してgⁱ != 1 mod pとなる値（このようなgを生成元と言う）
     • 2や5が使われることが多い
• 改ざん、中間者攻撃には弱い
  • 第三者がKC = g^c mod pをAさんに送った場合は秘密鍵がg^acとなってしまい、これは盗聴したKAと自身の秘密cから簡単に計算可能

ElGamal暗号

• ElGamal暗号
  • Diffie-Hellman鍵交換に基づく非対称暗号化アルゴリズムで、任意の巡回群G上で定義可能
  • 離散対数問題の難しさを担保とした（正確にはCDH仮定のもとで）公開鍵暗号アルゴリズムの1つ
  • ElGamal暗号はZp上での暗号
  • 一般ElGamal暗号はそれを拡張して任意の巡回群を使えるようにしたもの？
    • 巡回群：楕円曲線、（法nの）既約剰余類群
    • 普通のElGamal暗号では位数p-1が合成数になってしまうので、位数が素数になるものを考えるらしい
    • https://mitsu1119.github.io/blog/p/%E7%BE%A4%E3%81%A7%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B-elgamal/
• （法nの）既約剰余類群でのアルゴリズム
  • 鍵生成
    1. p = 2q+1を満たす素数p,qを用意する
       • pを安全素数, qをソフィー・ジェルマン素数と呼ぶ
    2. 法pの既約剰余類群を生成するための生成元gを選ぶ（何言っているのか分からん）
    3. 秘密鍵xを1＜x＜q-1の範囲からランダムに選んで h = g^x mod pを計算する
    4. 公開鍵(p,q,g,h), 秘密鍵(x)となる
       • 「離散対数問題の難しさからg,h,pからxを求めるのは難しい」となる
  • 暗号化
    1. 0からq-1の範囲からランダムな値rを選ぶ
    2. c1 = g^r mod p, c2 = m * h^r mod p を計算。(c1, c2)が暗号文となる
       • ランダム要素が入るのでRSAとは違い、暗号文が2つで、かつ、非決定的な暗号文となる。
       • このrも離散対数問題的に逆算できないようになっていて、かつ、共有しなくても復号可能（使ったら捨てる）
  • 復号 m = c2 * (c1 ^ x) ^ (-1) mod p
• 乗法準同型性を持つ
  • mxの暗号文(cx1, cx2, rx)とmyの暗号文(cy1, cy2, ry)の場合、暗号文(cx1cy1, cx2cy2)はmx*myをrx+ryを使って暗号化したことになる
• 脆弱なElGamal暗号
  • 乱数rの流用
    • 流用されている2つの暗号文が手に入ってしまうと、片方が復号化された場合にもう片方も復号できてしまうようになる
  • 危険な法pの使用
    • 安全素数じゃないと危ない
    • Pohlig-Hellmanと効率的な離散対数問題へのアルゴリズム Baby-step Giant-step法で解ける確率が上がる
      • SageMathのdiscrete_log関数を使って離散対数問題を解いてくれる（内部でPohlig-Hellman使われてる）
  • 第三者は復号はできないが、メッセージの値は改変できる可能性がある。暗号文を整数倍すれば、復号文も整数倍される？
• 平方剰余のルジャンドル記号を使うことで偶奇性は判定が可能
  • zer0pts CTF 2021 janken vs yoshiking https://blog.y011d4.com/20210307-zer0pts-ctf-writeup#janken-vs-yoshiking

ElGamal署名

• 実際はElGamal署名から派生したDSAが良く使われる
• 派生したDSAというデジタル署名方式がある
• 鍵生成
  • 大きな素数pを選択
  • pを法とする原始根gを選択
  • 秘密鍵xを(1,p-1)の範囲でランダムに選択
  • y=g^x mod pを計算し、公開鍵(p,g,y)を作る
• 署名生成
  • (1,p-1)かつgcd(k,p-1)=1となる乱数kを選択
  • r=g^k mod pを計算
  • s=(H(m)-xr)/k mod (p-1)を計算
  • (r,s)が署名
• 署名検証
  • rが(0,p)、sが(0,p-1)の範囲にあることを確認
  • g^H(m) = y^r * r^s mod pであることを確認
• 注意点
  • kは予測不可能でないといけない
  • kの再利用により秘密鍵が漏洩する
    • kが共通であり、既知のメッセージm1とm2、またそれらの署名(r,s1), (r,s2)が分かっているとき
    • s1 = (H(m1)-xr) / k
    • s2 = (H(m2)-xr) / k
    • 引くと、s2 - s1 = (H(m2) - H(m1)) / kとなり、k以外は既知なのでkが求まる
    • kが求まれば、s1 = (H(m1)-xr) / kからxが導けて秘密鍵が漏えいする。

Schnorr（シュノア）署名

• DLP(:離散対数問題)を数学的根拠とする署名方式
  • DSAやECDSAの基礎となっている
• アルゴリズム
  • 用意：巨大な素数q, qと互いに素な整数g, 署名対象m, 秘密鍵である整数s
  • 以下、署名対象をmとする
  • 署名作成
    1. 適当な乱数 r を作成する
    2. ハッシュ関数Hを用いて、e := H(m;g^r)を計算する
    3. 前のステップで求めたeを用いて y = r-se を計算する
    4. (y, e)が電子署名
  • 署名検証
    • 公開鍵としてp=g^sが公開される
    • e' := H(m;g^ype)を計算し、e=e'になることを確認する
  • 検証時の式を見ると変数eが式の両辺に現れている自己言及型の式となっている。ハッシュ関数も使われており、そのようなeを見つけるのは難しそうであるが、実際はp=g^sによりyを調整することで（署名作成の手順3）eを簡単に求められる
    • このようにある情報を知っていれば簡単に答えが計算できてしまう処理のことをトラップドア関数と言う
• セキュリティ
  • 巨大素数qや整数gを適切に選ばないと署名が偽装できるかも
    • 離散対数問題が簡単になって、p=g^sが計算できsが漏れる
    • 安全な選び方は原論文に書いてあるとのこと
      • https://blog.visvirial.com/articles/721 日本語でここに書いてあるが、正直読み方が分からん
  • 乱数r
    • 使いまわすと秘密鍵sが漏れる
      • y1=r-se1, y2=r-se2となり、r,sが未知の二次方程式になるので解けばsが得られてしまう
    • 安全でない乱数生成も推測によりrが分かればsが漏洩してしまう

DSA: Digital Signature Algorithm

• 現状は利用には推奨されない
• 歴史
  • 1991年にNISTによって、DSS: Digital signature Standardでの目的として提唱
  • 1993年 FIPS 196として標準化され、2013年までに何度か改訂されている
    • なお、FIPS 186-5により、新たにデジタル署名を行うことは推奨されなくなった
• DSA: ElGamal署名の改良版の1つであり、同様に離散対数問題の困難性に基づく電子署名方式
• 問題
  • TSGCTF 2021 - This is DSA https://blog.y011d4.com/20211005-tsgctf-writeup
    • 条件の1つを消して解く問題