素因数分解
いわゆる分枝限定法で、の半分程度のbit(実験によると大体53%〜が精度良く機能する)が分かっているときに素因数分解できる方法 ↓のコードでは分かっていると行ったbitのうち下位何bitかがエラーのケースに対応している。あと aeroctf と branch_and_prune …
#HackTM_CTF_Quals_2023 #good_challenges_2023 from math import gcd from Crypto.Util.number import bytes_to_long, isPrime from secret import p, q, x1, y1, x2, y2, e, flag # properties of secret variables assert isPrime(p) and p.bit_length() …
#ricerca_ctf_2023 #RSA #Suspicious_Prime #素因数分解 https://furutsuki.hatenablog.com/entry/2023/04/23/143704#Rotated-Secret-Analysis
#midnight_sun_ctf_qualifiers_2023 p = random_prime(2**1024) q = random_prime(2**1024) a = randint(0, 2**1024) b = randint(0, 2**1024) def read_flag(file='flag.txt'): with open(file, 'rb') as fin: flag = fin.read() return flag def pad_flag(…
#n1ctf_2020 wakaran https://rkm0959.tistory.com/167 RSA LLL ここでは序盤の素因数分解パートだけを取り扱う。そのあとはLWEなので from Crypto.Util.number import getRandomNBitInteger import timeout_decorator mark = 3**66 @timeout_decorator.time…
#tsg_live_ctf_10 #!/usr/bin/python3 from Crypto.Util.number import getPrime from flag import flag from sympy import nextprime dummy = b"GSTDIVE{this is a dummy}" dm = int.from_bytes(dummy,'little') assert(len(flag)==61) import secrets flag…
#aeroctf2021 #good_challenges_2021 #!/usr/bin/env python3.8 from gmpy import next_prime from random import getrandbits def bytes_to_long(data): return int.from_bytes(data, 'big') class Wardrobe: @staticmethod def create_boggarts(fear, dang…
univariate coppersmith method multivariate coppersmith 多項式の上の小さい根または上の小さい根を多項式時間で求めるアルゴリズム。つまり または となるようなを求めるということ。Sagemathではsmall_roots というメソッドが生えている。 というパラメ…
#bsidesnoidactf from functools import reduce from operator import mul from secrets import token_bytes from sys import exit from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes def main(): a = getPrime(512) b = reduce(mul, …