#midnightsun2021finals ELFが渡される。 RSAでがもらえるオラクルがある。は32bitポインタの範囲内。 目的はを求めること。 LLLらしいがわかってない hpmv — Today at 7:03 PM Didn't even open some challenges Tabula was the best though, my favorite h…

NTRUの小さいインスタンス from Crypto.Util.number import * import gmpy2 import random length_bit = 4096 def generate_key(length_bit = 4096): q = getPrime(length_bit) f = random.getrandbits(length_bit/2) while True: g = random.getrandbits(le…

#cakectf2021 with open("flag.txt", "rb") as f: flag = list(f.read().strip()) def hadamard(M): d = M.determinant() x = 1.0 for row in M: x *= row.norm() return (d / x) ** (1.0/M.ncols()) def keygen(n, d): k = int(floor(sqrt(n) * d)) while T…

#angstromctf2021 #!/usr/bin/python from functools import reduce with open("flag", "r") as f: key = [ord(x) for x in f.read().strip()] def substitute(value): return (reduce(lambda x, y: x * value + y, key)) % 691 print("Enter a number and i…

#HITCON_CTF_2022 import os from Crypto.Util.number import bytes_to_long, getPrime from Crypto.Cipher import AES from Crypto.Util.Padding import pad from hashlib import sha256 from secret import flag p = getPrime(384) q = getPrime(384) n = …

#acsc2021 #good_challenges_2021 #!/usr/bin/env python3 import os import random import string with open('flag.txt', 'rb') as f: FLAG = f.read().strip() assert FLAG.startswith(b'ACSC{') assert FLAG.endswith(b'}') SECRET = FLAG[5:-1] assert l…

RSA Recovering cryptographic keys from partial information, by example 参考文献 Recovering cryptographic keys from partial information, by example eが小さく、mの大部分がわかっている時 のようなとき。 とおいて について だから、こののsmall ro…

#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…

LLL sageにはLLL が実装されているが、これは基本的に重たい処理であるし、magmaに実装されているLLL と比較すると遅い（らしい）。この速度の差は精度の差で、厳密な計算を行うとやはり遅く、浮動小数点を使った近似的な計算を行うLLLは多少早くなる。magma…

https://github.com/rkm0959/Inequality_Solving_with_CVP/ 変数を一つ減らすテク となるときに の次数が1でその具体的な値に興味がなければ、全体を の係数 で割って、 という不等式にすれば一変数減る これを 大きさのわかっている未知変数を直接求めない…

とに対して、次を満たす整数の組が存在する これはLLLを使って効率的に求められる def thues_lemma(a, mod): ''' Find small elements x, y such that a * x = y and |x| < sqrt(mod) and |y| < sqrt(mod). ''' R = Zmod(mod) A = matrix([ [1, a], [0, mod]…

#RCTF2021 from multiprocessing import Pool size = 2^7 flag = open("flag.txt", "rb").read() assert len(flag) == 22 assert flag[:5] == b"flag{" assert flag[-1:] == b"}" seed = flag[5:-1] # 128 bit seed = (int.from_bytes(seed,'big')<<104) + (…

#RSA #LLL from Crypto.Util.number import * from secrets import d, flag from os import urandom T = 10 def encrypt(data): num = bytes_to_long(data) p = getPrime(512) q = getPrime(512) n = p*q assert num < n phi = (p-1)*(q-1) e = inverse(d,ph…

#googlectf2021 #!/usr/bin/python3 import os import hashlib from cryptography.hazmat.backends import default_backend from cryptography.hazmat.primitives import padding from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, m…

#yoshicamp2020winter hellmanのPh.D 資料 Coppersmith-Aleksei-Udovenko.pdf 到達目標 Coppersmith's methodのお気持ちがわかる univariateな多項式に対してのCoppersmith's methodが実装できる multivariateな多項式に対してのCoppersmith's methodが実装…

#ECDSA / #DSA LLL の が小さくて（がsha1で決まるなど）、かつ複数のインスタンスを集められるときはHidden Number Problemになる なので、Hidden Number Problemの式と対応付けると次のようになる from hashlib import sha1 # secp256k1 p = 0xfffffffffff…

#CDT #SVP #LLL

#SECCON_CTF_2022_Quals #kurenaif from Crypto.Util.number import * from flag import flag p = getStrongPrime(512) q = getStrongPrime(512) e = 65537 n = p * q phi = (p - 1) * (q - 1) d = pow(e, -1, phi) print(f"n = {n}") print(f"e = {e}") pri…

#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 …

#bsidesnoidactf #good_challenges_2021 from decimal import Decimal, getcontext from Crypto.Util.number import bytes_to_long, getRandomNBitInteger def is_valid_privkey(n): if n < 0: return False c = n * 4 // 3 d = c.bit_length() a = d >> 1 i…

Wiener's_Attackをやるくらいならこれをやれ。 のときからがわかる という行列に対してLLLをやるといい感じになるし、普通にcoppersmithでといても良い def boneh_durfee(e, N): s = floor(sqrt(N)) M = Matrix([[e, s], [N, 0]]) Mred = M.LLL() D = [abs(M…

from hash import secureHash import SocketServer import string import random from text import * import os from hashlib import sha256 PORT = 2000 ROUNDS = 10 TIMEOUT = 120 sigma = string.ascii_letters + string.digits + "!@#$%^&*()-_=+[{]}<>.…

print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024)) # -0.757848646514436165305674088364798107415772156823526394781277032859370615544627343198300308302394419345163450113384406222231838091222846932198471177164033…

#bsidesahmedabadctf_2021 import os from Crypto.Util.number import getPrime, getRandomRange with open("flag.txt", "rb") as f: m = f.read().strip() m += os.urandom(111 - len(m)) m = int.from_bytes(m, "big") xs = [] for i in range(11): p = ge…

#seccon2021 #kurenaif import signal from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime import random from flag import flag message = b"" for _ in range(128): message += b"o" if random.getrandbits(1) == 1 else b"O" M = ge…

RSA from Crypto.Util.number import getPrime, GCD from flag import FLAG import random def egcd(a, b): r0, r1 = a, b s0, s1 = 1, 0 t0, t1 = 0, 1 while r1 > 0: q = r0 // r1 r0, r1 = r1, r0 % r1 s0, s1 = s1, s0 - q * s1 t0, t1 = t1, t0 - q * t…

で 既知、未知 このとき次の行列のLLLでを求められることがある。はの最大値 ? なんで なんだろう → 符号はあんまり関係なさそう の形でも解けそうな気がしないか？ → そういう形にならない。基本的に と計算するため p = random_prime(1<<256) n = 10 max_x…

#3kCTF-2021 from Crypto.Util.number import inverse import hashlib import os rol = lambda val, r_bits, max_bits: (val << r_bits%max_bits) & (2**max_bits-1) | ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits))) class Random(): def __in…

解ける暗号。超増加列を用いた場合に部分和問題が簡単に解けることを利用して復号を行い、超増加列を鍵とすると簡単に解けてしまうため、各をと変換して一般の数列にすることで暗号化鍵からの復号を妨げている。 暗号文は一つの数値に、秘密鍵や公開鍵は数列…

#TSGCTF_2021 #hakatashi require 'openssl' require 'digest' STDOUT.sync = true class OpenSSL::PKey::EC::Point def xy n = to_bn(:uncompressed).to_i mask = (1 << group.degree) - 1 return (n >> group.degree) & mask, n & mask end alias_method :…