RSAで秘密鍵dの下位bitがある程度わかっているときに使える nのbit数の半分程度のbit数がわかっていて、 pとqが近い時に成功したりしなかったりする。MultiPrimeだともうちょっとbit数がいるっぽい。3/4くらい？ from Crypto.Util.number import getPrime, i…

#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://www.sebven.com/ctf/my-challs.html

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

#inctf2021 #!/usr/bin/python3 from random import getrandbits as rand from gmpy2 import next_prime, invert import pickle FLAG = open('flag.txt', 'rb').read() BUF = 16 def encrypt(msg, key): msg = format(int(msg.hex(), 16), f'0{len(msg)*8}b'…

#inctf2021 import os, hashlib, pickle from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad key = os.urandom(4) FLAG = open('flag.txt', 'rb').read() p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF …

#!/usr/bin/env python3 from random import getrandbits, randrange def generate(): IV = 532645365660741748592492683919913241393173602551561153678419663766604876396695082772115623037919135095305534947595527762871071624714167681814698732667699…

#AES #CTRモード #!/usr/bin/env python3 from Crypto.PublicKey import RSA, ECC import json from hashlib import sha256 from Crypto.Cipher import AES, PKCS1_OAEP from base64 import b64decode from Crypto.Signature import DSS from Crypto.Hash im…

#hsctf8 import random var("x y") flag = int(open('flag.txt','rb').read().hex(),16) xs = [random.randint(1,256) for i in range(9)] ys = [random.randint(1,256) for i in range(9)] assert not any([xs[i]==ys[i] for i in range(9)]) c = [random.r…

鍵生成 parameter ：↑で出てきたようにの値はだったりする ：暗号化に使うパラメータ。誤差の大きさ として格子の基底とする。このときは短いベクトルで、具体的にはのように選ぶ（where , さらに要素が整数かつ、であるようなを適当に選ぶ（と同様にの行列…

GF(p^1000) とかを作りたい気がするけど、遅い。そこで高速化テクです そもそもp-adic numberを使えばいい気がする まず、コンストラクタには生成多項式を与えたほうが早くなります 自分で作ってもsageに作らせても変わらない気がするけどなぜか早くなる def…

#fwordctf2021

#RSA であり、既知のときに有効な攻撃 多項式 とをそれぞれ上で考えると、なので、はを因数に持つ。従って一変数多項式のgcdをやると が得られる という攻撃。別にeが共通である必要はない from sage.all import * _, x = PolynomialRing(Zmod(N), name='x')…

#FireshellCTF2019 E, C, N が与えられているRSAの問題 パラメータが長くて収まりきらなかったのでgistに貼った https://gist.github.com/theoldmoon0602/b901a875f8a53b1ecdbcfbaeb9bf3d48 Nがあまりに大きすぎるので明らかに怪しい。とりあえずfactordb.co…

#FireshellCTF2019 #uninterested_challenge_list https://ctftime.org/task/7478 I forgot my email password and it was hacked. The hackers published 3000 password hashes incluiding mine. Please help me recover my password or else Adriano, the …

暗号化スキーム 秘密鍵 公開鍵 素数位数 を持つ巡回群 と、その生成元（原始根） 通常は巡回群として、乗法群が用いられる。 巡回群の位数と互いに素な値はその乗法巡回群の生成元となるから、は適当な素数を選ぶ 暗号化 をランダムに選んで、を計算し、 復…

#joseph #downunderctf2021 from string import ascii_lowercase, digits CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits n = len(CHARSET) def encrypt(msg, f): ct = '' for c in msg: ct += CHARSET[f.substitute(CHARSET.index(c))] return ct P.<x> </x>…

#cyber_apocalypse_ctf_2021 # The flag consists of only uppercase ascii letters # You do have to fix up the flag format yourself import string, hashlib, itertools def clean(x): return ''.join(c for c in x.upper() if c in string.ascii_letter…

#cryptoctf2021 #!/usr/bin/env python3 from Cryptodome.Cipher import AES import os import time import sys import random from flag import flag passphrase = b'HungryTimberWolf' def encrypt(msg, passphrase, niv): msg_header = 'EPOCH:' + str(in…

#cryptoctf2021 #!/usr/bin/python3 from Crypto.Util.number import * from gmpy2 import * from secret import * from flag import flag global nbit nbit = 1024 def keygen(nbit): while True: p, q = [getStrongPrime(nbit) for _ in '01'] if p % 4 ==…

#cryptoctf2021 #!/usr/bin/env python3 from Crypto.Util.number import * from gmpy2 import gcd from random import randint import sys import hashlib from flag import flag def lcm(a, b): return (a * b) // gcd(a,b) def gen_params(nbit): p, q = …

#cryptoctf2021 #!/usr/bin/env python3 from Crypto.Util.number import * from flag import flag nbit = 64 while True: p, q = getPrime(nbit), getPrime(nbit) P = int(str(p) + str(q)) Q = int(str(q) + str(p)) PP = int(str(P) + str(Q)) QQ = int(s…

#cryptoctf2021 #!/usr/bin/env python3 from sage.all import * from flag import flag n = 43216667049953267964807040003094883441902922285265979216983383601881964164181 U = 1823029494546684219302946481817610962847341445869345527252784978012143…

RSAの典型 とが共通でが異なる複数の暗号文を与えられた時、が復号できるというもの。ただし http://elliptic-shiho.hatenablog.com/entry/2015/12/14/043745 拡張ユークリッドの互除法を用いてを満たすX, Yを探す。こういうX, Yを使うとmが導出できるらしい…

N = 7994357243619412096346425559023154359080581236053314383870017985493384535205504119550400345883826817342615519489342317081121882143293857751974750159008864626782238232216635048703034178108919145901836276953638225815237056415040851559962…

multiple times pad

検証可能な暗号（復号の途中に不正な暗号を検出できる） 加法準同型性を持つ （ベースが Paillier暗号なんだな） 鍵生成 安全素数 を選び、 を計算する と をランダムに選ぶ を計算する 適当なハッシュ用の鍵 を生成する 公開鍵： 秘密鍵： パラメータ： 暗…

#cyber_apocalypse_ctf_2021 from Crypto.Util.number import bytes_to_long, getPrime from secrets import FLAG def gen_key(): from secrets import a,b E1 = EllipticCurve(F, [a,b]) assert E.is_isomorphic(E1) key = - F(1728) * F(4*a)^3 / F(E1.dis…

中国人剰余定理 CRT