DLP from Crypto.Util.number import * from sage.all import * def gen_weak_prime(size, smooth): """ generate approximately size-bit prime p which p-1 factorized to p_1 * p_2 * ... * p_n and p_n is up to smooth-bit (it means that p-1 is <smooth>-smoo</smooth>…

#angstromCTF2019 https://ctftime.org/task/8340 DLP https://furutsuki.hatenablog.com/entry/2019/04/25/143959#Crypto-100pts-Paint

離散対数問題に対するアプローチの一つ。 DLPでもECDLPでも同じアルゴリズムが適用できる。 DLPに対するPohlig-Hellman Attack 前提として、巡回群 の位数 が次のように素因数分解可能であるとする。よくあるのは素数 を法とする乗法群で、その位数はなので…

RSA DLP #!/usr/bin/env python3 # -*- coding:utf-8 -*- from Crypto.Util.number import * from gmpy2 import invert from hashlib import sha256 import string import os import random from secret import flag, e assert e.bit_length() == 477 BITS =…

DLPやECDLPを解く手法。乱択アルゴリズム [** Pollard's for ECDLP] def pollard_rho(P, Q, G, order): """ Q = xP G: generator """ a, b, x = 0, 0, (1, 0) A, B, X = a, b, x def walk(a, b, x): if x[0] % 3 == 0: return (a*2) % order, (b*2) % order,…

#joseph #downunderctf2021 def G_add(A, B): x1, y1 = A x2, y2 = B return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p) def G_mul(A, k): out = (1, 0) while k > 0: if k & 1: out = G_add(out, A) A = G_add(A, A) k >>= 1 return out def …

ECDLPとも 有限体上ではからを求めることは容易だがその逆は困難, これを求める問題を離散対数問題(DLP)と言った 楕円曲線上では整数と楕円曲線上の点から、楕円曲線上の点を計算するのは簡単だが、その逆は難しい。からを求める問題を#### 楕円離散対数問題…

entropoid-attack.tar.gz https://eprint.iacr.org/2021/583.pdf https://eprint.iacr.org/2021/1472.pdf よく分かってないけどそのうちCTFに出るでしょ Abstract entropoidと呼ばれるDLPベースの耐量子暗号が提案されていた。これは分配多元環（non associa…