第一屆OpenHarmonyCTF–Crypto–WriteUp
Ea5y_rsa
-
題目附件解壓后尋找有用的源代碼：
// RsaUtil import { cryptoFramework } from '@kit.CryptoArchitectureKit'; import { buffer } from '@kit.ArkTS';class RsaUtil{private keyPair: cryptoFramework.KeyPair | null = null;constructor() {let keyGenerator = cryptoFramework.createAsyKeyGenerator('RSA1024');this.keyPair = keyGenerator.generateKeyPairSync();}encrypt(data: string): cryptoFramework.DataBlob{let plainText: cryptoFramework.DataBlob = { data: new Uint8Array(buffer.from(data, 'utf-8').buffer) };if(this.keyPair != null){return this.rsaEncryptBySegment(this.keyPair.pubKey, plainText);}else{console.error('Key is null');return plainText;}}rsaEncryptBySegment(pubKey: cryptoFramework.PubKey, plainText: cryptoFramework.DataBlob) {let cipher = cryptoFramework.createCipher('RSA1024|PKCS1');cipher.initSync(cryptoFramework.CryptoMode.ENCRYPT_MODE, pubKey, null);let plainTextSplitLen = 64;let cipherText = new Uint8Array();for (let i = 0; i < plainText.data.length; i += plainTextSplitLen ) {let updateMessage = plainText.data.subarray(i, i + plainTextSplitLen );let updateMessageBlob: cryptoFramework.DataBlob = { data: updateMessage };let updateOutput = cipher.doFinalSync(updateMessageBlob);let mergeText = new Uint8Array(cipherText.length + updateOutput.data.length);mergeText.set(cipherText);mergeText.set(updateOutput.data, cipherText.length);cipherText = mergeText;}let cipherBlob: cryptoFramework.DataBlob = { data: cipherText };return cipherBlob;}getGift(): number[]{let gift: number[] = [0];if(this.keyPair != null){let pri = this.keyPair.priKey.getEncoded().data;for(let i: number = 7; i < 285; i++){gift.push(pri[i]);}}return gift;} }export default new RsaUtil();RSA工具類中提取的關鍵信息就是對明文信息進行了
RSA1024|PKCS1的加密，同時gift中包含著密鑰的相關信息。my gift: 0,48,13,6,9,42,134,72,134,247,13,1,1,1,5,0,4,130,2,98,48,130,2,94,2,1,0,2,129,129,0,162,241,252,198,79,226,203,150,170,211,175,5,127,220,154,215,250,190,125,3,43,15,214,239,122,148,175,20,208,173,241,85,168,92,181,110,220,162,25,205,159,96,119,180,19,33,9,52,34,137,4,102,166,195,142,204,1,247,140,141,184,92,14,162,123,208,160,102,112,154,194,130,104,139,141,10,54,148,160,164,100,245,208,41,39,103,160,135,99,108,15,231,219,255,249,35,114,131,108,70,144,182,118,253,222,115,181,71,155,70,135,141,36,73,221,205,146,31,8,55,181,46,111,127,208,101,185,221,2,3,1,0,1,2,129,128,43,13,141,32,72,211,63,191,155,123,58,239,85,13,80,204,104,48,20,143,213,188,229,169,120,213,248,60,163,182,145,225,116,14,170,209,147,242,48,167,39,201,49,87,159,6,71,140,66,227,185,9,246,94,13,72,209,236,58,114,231,151,75,54,47,89,245,211,248,113,162,189,101,189,68,168,165,3,221,23,176,183,78,56,179,150,198,63,126,131,223,165,239,32,59,158,187,205,223,211,228,55,107,19,136,241,169,206,131,34,95,225// Index import { cryptoFramework } from '@kit.CryptoArchitectureKit'; import { data } from '@kit.TelephonyKit'; import { util } from '@kit.ArkTS'; import RsaUtil from '../util/RsaUtil' import promptAction from '@ohos.promptAction';@Entry @Component struct Index {@State message: string = 'EaSy_rsa';@State flag: string = '';build() {Column() {Text(this.message).fontSize(32).fontWeight(FontWeight.Bold).fontColor(Color.Black).margin({ bottom: 40 }).textShadow({ radius: 2, color: Color.Blue, offsetX: 1, offsetY: 1 })TextInput({ placeholder: 'Input the flag here' }).placeholderColor(Color.Gray).placeholderFont({ size: 16 }).height(56).width('80%').padding(10).margin({ bottom: 20 }).borderRadius(8).backgroundColor(Color.White).onChange((data) => {this.flag = data;})Button('Check Flag', { type: ButtonType.Capsule, stateEffect: true }).width('50%').height(45).backgroundColor('#2196F3').margin({ top: 20 }).opacity(0.9).onClick(() => {this.check();}).animation({ curve: 'ease-in-out', duration: 200 }) // 修改這里}.width('100%').height('100%').justifyContent(FlexAlign.Center).backgroundColor('#F5F5F5').padding(20)}check(){let encryptText = RsaUtil.encrypt(this.flag);let base64 = new util.Base64Helper();let c = base64.encodeToStringSync(encryptText.data);if(c === 'nlRTOIr7P61VxeNDiPtFd65VCBJWhKlpSMF+g7Fib3VYHZYc/kgNWeFHSMvcgsqWuBCfMkB90SPQDR6hKvaxhYrqLAg/8+rRWqZbL7hXD3s2JA92V8zgx18r9zmekS28UiTUTUZDkkAhhkrWFvdx3gqgxGwj/l+DX82StHiyyOo='){promptAction.showToast({message: "Wow, you find the true flag"})}else{promptAction.showToast({message: "oh, Sorry. But In my Log, this is a gift for you"})let gift = RsaUtil.getGift();console.log('my gift:', gift);}} }針對于程序運行后的輸入校驗的函數
check()函數中包含相應的密文。 -
針對于
gift的內容，是針對于公鑰解析之后的16進制的數據不斷進行輸出的結果，我們進行16進制的還原即可獲取密鑰解析的結果：# data parsing my_gift = [0, 48, 13, 6, 9, 42, 134, 72, 134, 247, 13, 1, 1, 1, 5, 0, 4, 130, 2, 98, 48, 130, 2, 94, 2, 1, 0, 2, 129, 129, 0, 162, 241, 252, 198, 79, 226, 203, 150, 170, 211, 175, 5, 127, 220, 154, 215, 250, 190, 125, 3, 43, 15, 214, 239, 122, 148, 175, 20, 208, 173, 241, 85, 168, 92, 181, 110, 220, 162, 25, 205, 159, 96, 119, 180, 19, 33, 9, 52, 34, 137, 4, 102, 166, 195, 142, 204, 1, 247, 140, 141, 184, 92, 14, 162, 123, 208, 160, 102, 112, 154, 194, 130, 104, 139, 141, 10, 54, 148, 160, 164, 100, 245, 208, 41, 39, 103, 160, 135, 99, 108, 15, 231, 219, 255, 249, 35, 114, 131, 108, 70, 144, 182, 118, 253, 222, 115, 181, 71, 155, 70, 135, 141, 36, 73, 221, 205, 146, 31, 8, 55, 181, 46, 111, 127, 208, 101, 185, 221, 2, 3, 1, 0, 1, 2, 129, 128, 43, 13, 141, 32, 72, 211, 63, 191, 155, 123, 58, 239, 85, 13, 80, 204, 104, 48, 20, 143, 213, 188, 229, 169, 120, 213, 248, 60, 163, 182, 145, 225, 116, 14, 170, 209, 147, 242, 48, 167, 39, 201, 49, 87, 159, 6, 71, 140, 66, 227, 185, 9, 246, 94, 13, 72, 209, 236, 58, 114, 231, 151, 75, 54, 47, 89, 245, 211, 248, 113, 162, 189, 101, 189, 68, 168, 165, 3, 221, 23, 176, 183, 78, 56, 179, 150, 198, 63, 126, 131, 223, 165, 239, 32, 59, 158, 187, 205, 223, 211, 228, 55, 107, 19, 136, 241, 169, 206, 131, 34, 95, 225] key = "".join(f"{i:02x}" for i in my_gift) # print(key)n = 0xa2f1fcc64fe2cb96aad3af057fdc9ad7fabe7d032b0fd6ef7a94af14d0adf155a85cb56edca219cd9f6077b41321093422890466a6c38ecc01f78c8db85c0ea27bd0a066709ac282688b8d0a3694a0a464f5d0292767a087636c0fe7dbfff92372836c4690b676fdde73b5479b46878d2449ddcd921f0837b52e6f7fd065b9dd e = 0x010001 d = 0x2b0d8d2048d33fbf9b7b3aef550d50cc6830148fd5bce5a978d5f83ca3b691e1740eaad193f230a727c931579f06478c42e3b909f65e0d48d1ec3a72e7974b362f59f5d3f871a2bd65bd44a8a503dd17b0b74e38b396c63f7e83dfa5ef203b9ebbcddfd3e4376b1388f1a9ce83225fe1 # print(d.bit_length()) 894在嘗試利用
d進行解密之后，發現是亂碼，再從解析之后key之后的數據可以查看完整的d的長度為0x80 = 1024，但是我們能得到的之后d的前894位。 -
由此，這道題我們轉化為
d的高位泄露題型：from Crypto.Util.number import * from sage.all import * import timen = 0xa2f1fcc64fe2cb96aad3af057fdc9ad7fabe7d032b0fd6ef7a94af14d0adf155a85cb56edca219cd9f6077b41321093422890466a6c38ecc01f78c8db85c0ea27bd0a066709ac282688b8d0a3694a0a464f5d0292767a087636c0fe7dbfff92372836c4690b676fdde73b5479b46878d2449ddcd921f0837b52e6f7fd065b9dd e = 0x010001 d_high = 0x2b0d8d2048d33fbf9b7b3aef550d50cc6830148fd5bce5a978d5f83ca3b691e1740eaad193f230a727c931579f06478c42e3b909f65e0d48d1ec3a72e7974b362f59f5d3f871a2bd65bd44a8a503dd17b0b74e38b396c63f7e83dfa5ef203b9ebbcddfd3e4376b1388f1a9ce83225fe1start = time.time()K = []for k in range(1, e + 1):x = bin(k * n // e)[2:400]if x == bin(d_high)[2:400]:K.append(k)num = 128 d_high = d_high << numdef partial_p(p0, n):PR = PolynomialRing(Zmod(n), 'x')x = PR.gen()f= p0 + xf = f.monic()roots = f.small_roots(X = 2 ** (num+10), beta = 0.4)if roots:x0 = roots[0]p = GCD(p0 + x0, n)return ZZ(p) if p else 0PR = PolynomialRing(RealField(1000), 'y') y = PR.gen() for k in K:f = e * d_high * y - k * y * (n - y + 1) + k * n - yroots=f.roots()if roots:for xx in roots:p0 = int(xx[0]) >> num << nump = partial_p(p0, n)if p and p != 0:print('p = ',p)end = time.time()print('The consuption of time:', end - start)""" The consuption of time: 0.1361241340637207 The consuption of time: 0.16749978065490723 p = 10609536873189439093987168655422489704742490285865890688702649130890409041577511059239614677033225205694500579690122694298869488312781472236774639205449577 p = 10785018847726402903608489620145982985685187179540701584989135330533906562092497479310200366886897809597950246066018976762887050300757980281186631033654357 The consuption of time: 0.20140624046325684 The consuption of time: 0.22362780570983887 """ -
針對于
c解析后的數據進行RSA解密即可：from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse from base64 import b64decodec = bytes_to_long(b64decode(r'nlRTOIr7P61VxeNDiPtFd65VCBJWhKlpSMF+g7Fib3VYHZYc/kgNWeFHSMvcgsqWuBCfMkB90SPQDR6hKvaxhYrqLAg/8+rRWqZbL7hXD3s2JA92V8zgx18r9zmekS28UiTUTUZDkkAhhkrWFvdx3gqgxGwj/l+DX82StHiyyOo=')) p = 10609536873189439093987168655422489704742490285865890688702649130890409041577511059239614677033225205694500579690122694298869488312781472236774639205449577 q = 10785018847726402903608489620145982985685187179540701584989135330533906562092497479310200366886897809597950246066018976762887050300757980281186631033654357 d = inverse(65537, (p - 1) * (q - 1)) print(long_to_bytes(pow(c, d, p * q))) """ b'\x02\xc4]\xe5\xcd\xd6\xb5\xec\x8a`\xadv\xb7\x9b\xb2b\x07\x0c\x0f\tFzN\xdbw\x92~\x10\x11lO\x1a\xec\x83\xa2\x08\xa4\xa3\xf7\x97Rb\xc2\x817\x92\xe9\xa7\x1f(\xbf\x8a\x14\xf7q$\xe4\x80\r"bC#T\xff>\x0fkh\xc5i;\xd8\xfc\xa1O\xc4\x8cw\x8f\xb0\xb9/\xa2C\x00flag{01D_W1Ne_in_4_n3W_80t7lE_HAh4hAH4h4}' flag{01D_W1Ne_in_4_n3W_80t7lE_HAh4hAH4h4} """
Weak_random
task
from secret import flag
import time
import os
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
import hashlibassert(len(flag)==32)def padding(message):padding_len = 16 - len(message)%16ret = hex(padding_len)[2:].zfill(2)return bytes.fromhex(ret*padding_len)+messagedef get_weak_entropy():time_now=time.time()%10000entropy_part1 = int(time_now) & 0xFFFF entropy_part2 = os.getpid() & 0xFFfinal_seed = entropy_part1 + (entropy_part2 << 8) random.seed(final_seed)key = random.getrandbits(128) return key
entropy_key=get_weak_entropy()
iv = os.urandom(16)
key_bytes = entropy_key.to_bytes(16, byteorder='big')
msg=padding(flag.encode())
aes = AES.new(key_bytes,AES.MODE_CBC,iv=iv)
enc = aes.encrypt(msg)
print(enc.hex())
check=hashlib.sha256(flag.encode('utf-8')).hexdigest()
print(check)
#enc=acbea7dd473392c6d437b5ed1bbdc7fc789713d5a54d0a20b89839459d65cf1a2e782c848b2b4873a60ec025f143ac8b
#check=555e303a72723931dcb77994e4c0e412001700bb89c656057f989b6da1d17bf3
analysis
-
分析賽題，針對于填充函數，由于
assert len(flag) == 32，所以填充內容我們可以知曉，也就是直接在flag前填充了16個\x10def padding(message):padding_len = 16 - len(message)%16ret = hex(padding_len)[2:].zfill(2)return bytes.fromhex(ret*padding_len) + messageflag = b'flag{this_is_a_32bits_test_flag}' assert len(flag) == 32 print(padding(flag)) # b'\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10flag{this_is_a_32bits_test_flag}' -
同時，
key利用隨機數進行選取，而且隨機數的種子采用時間進行，被限定在了0~10000的范圍內，因此，我們可以爆破種子，利用第一個隨機數當作key對第一組的密文與已知填充序列異或，獲得iv后進行AES解密，采用check判斷是否解密成功。
·exp
from Crypto.Cipher import AES
from pwn import xor
from tqdm import *
import random
import hashlibenc = bytes.fromhex("acbea7dd473392c6d437b5ed1bbdc7fc789713d5a54d0a20b89839459d65cf1a2e782c848b2b4873a60ec025f143ac8b")
check = "555e303a72723931dcb77994e4c0e412001700bb89c656057f989b6da1d17bf3"for i in tqdm(range(100000)):random.seed(i)key = random.getrandbits(128)aes = AES.new(key.to_bytes(16, byteorder='big'),AES.MODE_ECB)enc0 = enc[:16]enc1 = enc[16:32]enc2 = enc[32:]iv = xor(aes.decrypt(enc0), b'\x10' * 16)aes_new = AES.new(key.to_bytes(16, byteorder = 'big'),AES.MODE_CBC,iv = iv)m = aes_new.decrypt(enc)if hashlib.sha256(m[16:]).hexdigest() == check:print(b'flag{' + m[16:] + b'}')break
# 'flag{d7e6a465a90a8d5a1cf4f488d10a8279}'
Small Message For (SM4) Encryption
task
from gmssl import sm4, func
from os import urandom
from flag import FLAG, secret_messagedef xor(a, b):return bytes(x ^ y for x, y in zip(a, b))def encrypt(key, plaintext, iv):cipher = sm4.CryptSM4(sm4.SM4_ENCRYPT, 0)cipher.set_key(key, sm4.SM4_ENCRYPT)ciphertext = cipher.crypt_cbc(iv,plaintext)return ciphertextdef main():key = secret_messagewhile len(key) < 16:key += secret_messagekey = key[:16]iv = urandom(16)plaintext = b"My FLAG? If you want it, I'll let you have it... search for it! I left all of it at that place: " + FLAGassert len(plaintext) % 16 == 0, "The message must be a multiple of 16 bytes."ciphertext = encrypt(key, plaintext, iv)print(f"Ciphertext: {ciphertext.hex()}")print(f"What is this: {xor(key, iv).hex()}")if __name__ == "__main__":main()
analysis
- 經過初步加密算法分析，
xor與encrypt函數都很正常，但是在key的生成個過程中，可能出現重復字符串的情況：secret_message * m - 我們可以 通過爆破
secret_message的內容，之后利用其充當key，同時，我們擁有數據key ^ iv，由此，我們可以得到iv后進行解密，放解密后的明文格式與plaintext相同時表示解密正確。
exp
from gmssl import sm4
from itertools import product
from string import ascii_letters, digitskey_iv = bytes.fromhex('ee278c4e526ff15b8d308b6b18f83221')
ciphertext = bytes.fromhex('d9ea43b0d208aa168e4a275a69df3bc86051e756f9ca7959b68c6b23c9e1b69c''19e08b75938375a6be830d1844d8a6e368faf1ddffecea69b5abe00ac0d6e10d''6696be33d40e83a272072fbe131f98c82587011f61f2d58a020c8c54cf9b651a''bd740a3d55d36daa9c88cfc10a520ce4211fba4365ce98b82355b17c64dd2de4''800fc68df36cfa8a3fd05baac6970dcd'
)for l in range(1, 5):for guess in product(ascii_letters + digits, repeat = l):secret = ''.join(guess).encode()key = (secret * 16)[:16]iv = bytes(x ^ y for x, y in zip(key, key_iv))cipher = sm4.CryptSM4()cipher.set_key(key, sm4.SM4_DECRYPT)plain = cipher.crypt_cbc(iv, ciphertext)if b'My FLAG?' in plain:print(f"Secret: {secret.decode()}\nFlag: {plain.split(b': ')[-1]}")exit()
"""
Secret: sM
Flag: b'flag{tHe_m3s5ag3_1s_2_sMa11!11!}'
"""
Simple LLL
-
下載附件解壓之后有
output.txt文件與entry-default-unsigned.hap文件，后者后綴名改為.zip解壓。找到modules.abc文件，采用反編譯Java代碼：
public Object #~@0>#runMixer(Object functionObject, Object newTarget, Index this) {obj = this.flag;if ((this.flag.length < 6 ? 1 : 0) != 0) {this.output = "Flag too short!";return null;}if (istrue(("flag{" != obj.substring(0, 5) ? 1 : 0)) != null || isfalse(("}" != obj[obj.length - 1] ? 1 : 0)) == null) {this.output = "Invalid flag, must starts with `flag{` and ends with `}`";return null;}substring = obj.substring(5, obj.length - 1);if ((0 != (substring.length % 3) ? 1 : 0) != 0) {this.output = "Invalid key length (must be multiple of 3)";return null;}i = 0;getPrime = this.getPrime(215);getPrime2 = this.getPrime(128);getPrime3 = this.getPrime(170);r36 = [Object];obj2 = getiterator("Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof.".substring(0, 50));obj3 = obj2.next;i2 = 0;while (true) {callthisN = obj3();throw.ifnotobject(callthisN);if (istrue(callthisN.done) != null) {break;}r362 = callthisN.value;try {bytesToLong = this.bytesToLong(substring[i] + substring[i + 1] + substring[i + 2]);i += 3;r362 = (i >= substring.length ? 1 : 0);if (r362 != 0) {i = 0;}r36.push((this.getRandomBits(190) * getPrime) + ((this.modPow(getPrime2, bytesToLong, getPrime3) * BigInt(r362.charCodeAt(0))) % getPrime3));} catch (ExceptionI0 unused) {z = r362;if (istrue(i2) == null) {i2 = 1;obj4 = null;r363 = hole;try {obj5 = obj2.return;obj3 = obj5;r363 = (0 == obj5 ? 1 : 0);} catch (ExceptionI0 unused2) {}if (r363 == 0) {obj4 = obj3();throw(z);throw.ifnotobject(obj4);}}throw(z);}}this.output = "P: " + getPrime3 + ", G: " + getPrime2 + "\nEncrypted: [" + r36.join(", ") + "]";console.error("P: " + getPrime3 + "");console.error("G: " + getPrime2 + "");i3 = 0;obj6 = getiterator(r36);obj7 = obj6.next;i4 = 0;while (true) {callthisN2 = obj7();throw.ifnotobject(callthisN2);if (istrue(callthisN2.done) != null) {return null;}r364 = callthisN2.value;try {console.error("result[" + i3 + "]: " + r36[i3] + "");r364 = i3 + 1;i3 = r364;} catch (ExceptionI0 unused3) {z2 = r364;if (istrue(i4) == null) {i4 = 1;obj8 = null;r365 = hole;try {obj9 = obj6.return;obj7 = obj9;r365 = (0 == obj9 ? 1 : 0);} catch (ExceptionI0 unused4) {}if (r365 == 0) {obj8 = obj7();throw(z2);throw.ifnotobject(obj8);}}throw(z2);}}} -
重寫一下反編譯出的Java代碼找到清晰的加密邏輯，并且當作
oracle生成一組明文對方便后續進行測試：import java.math.BigInteger; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException;public class FlagEncryptor {private String output;// 主方法，用于測試public static void main(String[] args) {FlagEncryptor encryptor = new FlagEncryptor();// 示例flag，格式必須為 flag{...}，中間長度是3的倍數String testFlag = "flag{this_is_a_test_flag_chen_xing0}";Object result = encryptor.runMixer(null, null, new Index(testFlag));System.out.println("加密結果: " + encryptor.getOutput());}// 你的加密方法public Object runMixer(Object functionObject, Object newTarget, Index thisObj) {String obj = thisObj.getFlag();if (obj.length() < 6) {this.output = "Flag too short!";return null;}if (!obj.startsWith("flag{") || !obj.endsWith("}")) {this.output = "Invalid flag, must starts with `flag{` and ends with `}`";return null;}String substring = obj.substring(5, obj.length() - 1);if (substring.length() % 3 != 0) {this.output = "Invalid key length (must be multiple of 3)";return null;}BigInteger getPrime = getPrime(215);BigInteger getPrime2 = getPrime(128);BigInteger getPrime3 = getPrime(170);List<BigInteger> r36 = new ArrayList<>();String referenceText = "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof.";Iterator<Character> obj2 = getiterator(referenceText.substring(0, 50));int i = 0;while (obj2.hasNext()) {char r362 = obj2.next();try {BigInteger bytesToLong = bytesToLong(substring.charAt(i) + "" + substring.charAt(i + 1) + "" + substring.charAt(i + 2));i += 3;if (i >= substring.length()) {i = 0;}r36.add((getRandomBits(190).multiply(getPrime)).add((modPow(getPrime2, bytesToLong, getPrime3).multiply(BigInteger.valueOf(r362))).mod(getPrime3)));} catch (Exception unused) {throw new RuntimeException("Encryption error");}}this.output = "P: " + getPrime3 + ", G: " + getPrime2 + "\nEncrypted: [" + String.join(", ", r36.stream().map(Object::toString).toList()) + "]";System.err.println("P: " + getPrime3);System.err.println("G: " + getPrime2);for (int i3 = 0; i3 < r36.size(); i3++) {System.err.println("result[" + i3 + "]: " + r36.get(i3));}return null;}// 輔助方法實現private BigInteger getPrime(int bits) {return BigInteger.probablePrime(bits, new java.util.Random());}private BigInteger bytesToLong(String s) {byte[] bytes = s.getBytes();BigInteger result = BigInteger.ZERO;for (byte b : bytes) {result = result.shiftLeft(8).add(BigInteger.valueOf(b & 0xFF));}return result;}private BigInteger getRandomBits(int bits) {return new BigInteger(bits, new java.util.Random());}private BigInteger modPow(BigInteger base, BigInteger exponent, BigInteger modulus) {return base.modPow(exponent, modulus);}private Iterator<Character> getiterator(String s) {return new Iterator<Character>() {private int index = 0;@Overridepublic boolean hasNext() {return index < s.length();}@Overridepublic Character next() {if (!hasNext()) {throw new NoSuchElementException();}return s.charAt(index++);}};}public String getOutput() {return output;}// 用于傳遞flag的類static class Index {private final String flag;public Index(String flag) {this.flag = flag;}public String getFlag() {return flag;}} } /* P: 1227678060386418065400995844771942486039536259441739 G: 331662963504457731810383150499096488683 result[0]: 7163089502041006323390018131760983715575909017384396604763700412331961010273372971344683890752467240100145759038117579474 result[1]: 8924484098516481951956737240714463142632079222185769328514176882401940203031213319898197470035111609053242015349557703227 result[2]: 5770905316827930140465965333439321427237862988555921540827775170693712033804422628684119130442180714554934014424686244165 result[3]: 44796777786009227975216870876558660608538505321237079951238173246178921115268045768425614583998787864620981218778678149738 result[4]: 52824170520543359672545483957105315663311964272032944318187172244041271448010577573672491709729840224421988297671594447061 result[5]: 53494510524020982386967348364202586487294621106881422665454600107097089526639811793285007824176269221015084510387937955881 result[6]: 17413006230472598014607587247171782745954022824733381081072562540571919548331674199235754769259423952824430517291808095067 result[7]: 28561015738092884193503561851007792012312067473919281738227371939809014982592897535763912169756134161455449571106794004629 result[8]: 27691425667281138643501649079322041896743463256717619874317305556156500133633095540035666365991288335953044616094452025838 result[9]: 15460935755614534253304313018420314624350554809791802649435355508736659731170248066377303685318193146805492751486309600948 result[10]: 47539632657354662171326933730997921078448054033528209446111339464980073980736160541981357686386810875019109655347498509551 result[11]: 22402537488710054946911121403073792045938889639549210881926619696298720196550542817025910462141988594080567476149228201225 result[12]: 39373939700703498245312728020878034226199456898645129086419005581478531225410333382080586421033789193780910018953718151035 result[13]: 50393070404564103463296427550054748563006296808429533035189599904781417312773992077313879494620891573985025995990362427046 result[14]: 50560755469108181779253550796419467453822732550048232352976900111320965423447982234319500734441881533078267198679716868147 result[15]: 31053815510012537761453651023722475580313185793416028968397170841473474014991733203479964389038612632474500092627946654800 result[16]: 17591111664218390646540290263322438565991600566612830815563803378636955143566240425026196468583694483059211272195601294477 result[17]: 21986271608940066046025405157876742039438296612428439621847177171849082369085841042738511897780901916375329515475468255050 result[18]: 48034974317159155266039512640595298551952215288310340780274357988334207990708333015669498846106562573801769307770254498719 result[19]: 36004675831153886403936901946945223182376387792379251578563086664939536128564846737722629982722249147716340130788282945954 result[20]: 25073306668918940010167684618611275041628391430411769959226328074664670688685191087925351978453748613698597717497861346474 result[21]: 47469522007147549577221260501117452889420161959722717283742523186865006152915854789477010249718721160530837181537361829521 result[22]: 41891935134191484796016413205979896981074425551194362037778585019693019992030844397960200283229977001772348405208697700309 result[23]: 36386372600251449288495710440082322295559461723712993940948715847660372074073760992208866001633520363080646262787933903319 result[24]: 29317212004283478670307057049121747821157356830358076566443113892431638436943343021021157473224740231790844713718767067101 result[25]: 21886686267763551366850327615420094618204739576842569008517234610487301080404816796283498219466272199508410674824388040616 result[26]: 20411616429357779732793952120212825119292889187817657324394342285965345393312750668668063044583374788264814362683506227263 result[27]: 53485493262843658089882759154377406167778761476189476207624240342852281822261379986466322017093268857844105466313283823774 result[28]: 35161703042981482088228959097108586983849134734515301825611227285760422365330968935888437291612114032652294106056829860176 result[29]: 49041244092941384629503940760863482116972857047549456757616835964853038271098711432865566302116451460152269939117740057593 result[30]: 31841864808403717042432983181047885467783962186373075159516392266166433086716637660350827586825891142289947420329904397172 result[31]: 14873397763965609230542160625362991895482690326594922307480948955371485561630013298311219623240481876484895122454113843300 result[32]: 18755079546695641234254327109303965464905563355656591592515803329191098874367738498377318834760947965509194397144572374577 result[33]: 48159590525687264056408255917249184247320279026840747880728857996047984794382109903758476645530380992955421151010705361233 result[34]: 13696433901912863569715585620845682472394721015933569937855873093624441686849856868746673692555192411531595385072763066976 result[35]: 43320902403606357036982905703763521449172633179735247185797458051230426330315607880436541814545173301238408859251773255451 result[36]: 44883328646162685531058753390292082144083162945068689613838197042637885098741337621596460084257994429426933464335093779328 result[37]: 31294638574091737659605854947772659222294270740226223633446769986706942596097634583709348629396671918853616232134150377415 result[38]: 8632785800688087784188986361808984763246590115202389018828680238402338542959330951828710664987563680467024075096543541894 result[39]: 9440687306515579204340765250381212998995542938399316347145352808850526843584913908461085482621212648425242170705250976473 result[40]: 22055192243575904548117693067859137230859459284897513864929867456074778216946933420190144673326915473483280207002480248524 result[41]: 36662256253439928566474754448626000795159774467206452878102281057086452269711977669589200999159678382386938520261915826572 result[42]: 43534743115503358911335052278830519629466066620025308640055027020884055331535264596804530826510200771328990442203824809588 result[43]: 49876198109245109588927811843768268915518612551357890802422138704753641721397914661257895026971287029789081192086230843920 result[44]: 23354903974148749592917602089310872349463272210477701964802462432883907353202178071167857482270837136785700642169601441293 result[45]: 24235396818783083317684698571616840837442393440917930990071809125309451834848883941113360083969773773133587532949651716816 result[46]: 51094354782951038576756399716265129760176221490828533066126314025454263631388307898915176976397302901276114314442460068922 result[47]: 25739441338390059617103294927516010710186475729160704488952673143395953383460149721243433950367182259995055078242040837465 result[48]: 54589806361093209402779098389473263397993442808224363579809015671485210049016249978379542820809236402280193729208487997318 result[49]: 49377881825104725713748459802371358149166706091849232627767090936010790193632435209317051192856519926400090852246409590862 加密結果: P: 1227678060386418065400995844771942486039536259441739, G: 331662963504457731810383150499096488683 Encrypted: [7163089502041006323390018131760983715575909017384396604763700412331961010273372971344683890752467240100145759038117579474, 8924484098516481951956737240714463142632079222185769328514176882401940203031213319898197470035111609053242015349557703227, 5770905316827930140465965333439321427237862988555921540827775170693712033804422628684119130442180714554934014424686244165, 44796777786009227975216870876558660608538505321237079951238173246178921115268045768425614583998787864620981218778678149738, 52824170520543359672545483957105315663311964272032944318187172244041271448010577573672491709729840224421988297671594447061, 53494510524020982386967348364202586487294621106881422665454600107097089526639811793285007824176269221015084510387937955881, 17413006230472598014607587247171782745954022824733381081072562540571919548331674199235754769259423952824430517291808095067, 28561015738092884193503561851007792012312067473919281738227371939809014982592897535763912169756134161455449571106794004629, 27691425667281138643501649079322041896743463256717619874317305556156500133633095540035666365991288335953044616094452025838, 15460935755614534253304313018420314624350554809791802649435355508736659731170248066377303685318193146805492751486309600948, 47539632657354662171326933730997921078448054033528209446111339464980073980736160541981357686386810875019109655347498509551, 22402537488710054946911121403073792045938889639549210881926619696298720196550542817025910462141988594080567476149228201225, 39373939700703498245312728020878034226199456898645129086419005581478531225410333382080586421033789193780910018953718151035, 50393070404564103463296427550054748563006296808429533035189599904781417312773992077313879494620891573985025995990362427046, 50560755469108181779253550796419467453822732550048232352976900111320965423447982234319500734441881533078267198679716868147, 31053815510012537761453651023722475580313185793416028968397170841473474014991733203479964389038612632474500092627946654800, 17591111664218390646540290263322438565991600566612830815563803378636955143566240425026196468583694483059211272195601294477, 21986271608940066046025405157876742039438296612428439621847177171849082369085841042738511897780901916375329515475468255050, 48034974317159155266039512640595298551952215288310340780274357988334207990708333015669498846106562573801769307770254498719, 36004675831153886403936901946945223182376387792379251578563086664939536128564846737722629982722249147716340130788282945954, 25073306668918940010167684618611275041628391430411769959226328074664670688685191087925351978453748613698597717497861346474, 47469522007147549577221260501117452889420161959722717283742523186865006152915854789477010249718721160530837181537361829521, 41891935134191484796016413205979896981074425551194362037778585019693019992030844397960200283229977001772348405208697700309, 36386372600251449288495710440082322295559461723712993940948715847660372074073760992208866001633520363080646262787933903319, 29317212004283478670307057049121747821157356830358076566443113892431638436943343021021157473224740231790844713718767067101, 21886686267763551366850327615420094618204739576842569008517234610487301080404816796283498219466272199508410674824388040616, 20411616429357779732793952120212825119292889187817657324394342285965345393312750668668063044583374788264814362683506227263, 53485493262843658089882759154377406167778761476189476207624240342852281822261379986466322017093268857844105466313283823774, 35161703042981482088228959097108586983849134734515301825611227285760422365330968935888437291612114032652294106056829860176, 49041244092941384629503940760863482116972857047549456757616835964853038271098711432865566302116451460152269939117740057593, 31841864808403717042432983181047885467783962186373075159516392266166433086716637660350827586825891142289947420329904397172, 14873397763965609230542160625362991895482690326594922307480948955371485561630013298311219623240481876484895122454113843300, 18755079546695641234254327109303965464905563355656591592515803329191098874367738498377318834760947965509194397144572374577, 48159590525687264056408255917249184247320279026840747880728857996047984794382109903758476645530380992955421151010705361233, 13696433901912863569715585620845682472394721015933569937855873093624441686849856868746673692555192411531595385072763066976, 43320902403606357036982905703763521449172633179735247185797458051230426330315607880436541814545173301238408859251773255451, 44883328646162685531058753390292082144083162945068689613838197042637885098741337621596460084257994429426933464335093779328, 31294638574091737659605854947772659222294270740226223633446769986706942596097634583709348629396671918853616232134150377415, 8632785800688087784188986361808984763246590115202389018828680238402338542959330951828710664987563680467024075096543541894, 9440687306515579204340765250381212998995542938399316347145352808850526843584913908461085482621212648425242170705250976473, 22055192243575904548117693067859137230859459284897513864929867456074778216946933420190144673326915473483280207002480248524, 36662256253439928566474754448626000795159774467206452878102281057086452269711977669589200999159678382386938520261915826572, 43534743115503358911335052278830519629466066620025308640055027020884055331535264596804530826510200771328990442203824809588, 49876198109245109588927811843768268915518612551357890802422138704753641721397914661257895026971287029789081192086230843920, 23354903974148749592917602089310872349463272210477701964802462432883907353202178071167857482270837136785700642169601441293, 24235396818783083317684698571616840837442393440917930990071809125309451834848883941113360083969773773133587532949651716816, 51094354782951038576756399716265129760176221490828533066126314025454263631388307898915176976397302901276114314442460068922, 25739441338390059617103294927516010710186475729160704488952673143395953383460149721243433950367182259995055078242040837465, 54589806361093209402779098389473263397993442808224363579809015671485210049016249978379542820809236402280193729208487997318, 49377881825104725713748459802371358149166706091849232627767090936010790193632435209317051192856519926400090852246409590862]*/
analysis
p=getPrime(215);g=getPrime(128);q=getPrime(170).flag=b′flag{S}′對S中每三個字節進行分組，分別bytes_to_long為si,S=[s1,s2??,sn]提取參考文本前5個字節設為T=[t1,t2,??,s50]，其中S循環使用，T迭代使用ci=k?p+[(gnj?mod?q)?ord(ri)?mod?q];k:(k=getRandomBits(190))一個190bit的隨機大整數Output:p,g,C=[c1,c2,?c50]從加密流程可以看出這是一個agcd問題，求取q(下文p1)，最后利用oracle爆破三個字節與C進行比對。
p = getPrime(215);g = getPrime(128);q = getPrime(170).flag = b'flag\{S\}'\\
對S中每三個字節進行分組，分別bytes\_to\_long為s_i,S = [s_1,s_2\cdots,s_n]\\
提取參考文本前5個字節設為T=[t_1,t_2,\cdots,s_{50}]，其中S循環使用，T迭代使用\\
c_i=k * p + [(g^{n_j}\ mod\ q) * ord(r_i)\ mod\ q];k:(k=getRandomBits(190))一個190bit的隨機大整數\\
Output:p,g,C=[c_1,c_2,\cdots c_50]\\
從加密流程可以看出這是一個agcd問題，求取q(下文p_1)，最后利用oracle爆破三個字節與C進行比對。
p=getPrime(215);g=getPrime(128);q=getPrime(170).flag=b′flag{S}′對S中每三個字節進行分組，分別bytes_to_long為si?,S=[s1?,s2??,sn?]提取參考文本前5個字節設為T=[t1?,t2?,?,s50?]，其中S循環使用，T迭代使用ci?=k?p+[(gnj??mod?q)?ord(ri?)?mod?q];k:(k=getRandomBits(190))一個190bit的隨機大整數Output:p,g,C=[c1?,c2?,?c5?0]從加密流程可以看出這是一個agcd問題，求取q(下文p1?)，最后利用oracle爆破三個字節與C進行比對。
exp_test
from Crypto.Util.number import *
from sage.all import *# 將out列表中的元素轉換為Python整數
out = [int(n) for n in [7163089502041006323390018131760983715575909017384396604763700412331961010273372971344683890752467240100145759038117579474, 8924484098516481951956737240714463142632079222185769328514176882401940203031213319898197470035111609053242015349557703227, 5770905316827930140465965333439321427237862988555921540827775170693712033804422628684119130442180714554934014424686244165, 44796777786009227975216870876558660608538505321237079951238173246178921115268045768425614583998787864620981218778678149738, 52824170520543359672545483957105315663311964272032944318187172244041271448010577573672491709729840224421988297671594447061, 53494510524020982386967348364202586487294621106881422665454600107097089526639811793285007824176269221015084510387937955881, 17413006230472598014607587247171782745954022824733381081072562540571919548331674199235754769259423952824430517291808095067, 28561015738092884193503561851007792012312067473919281738227371939809014982592897535763912169756134161455449571106794004629, 27691425667281138643501649079322041896743463256717619874317305556156500133633095540035666365991288335953044616094452025838, 15460935755614534253304313018420314624350554809791802649435355508736659731170248066377303685318193146805492751486309600948, 47539632657354662171326933730997921078448054033528209446111339464980073980736160541981357686386810875019109655347498509551, 22402537488710054946911121403073792045938889639549210881926619696298720196550542817025910462141988594080567476149228201225, 39373939700703498245312728020878034226199456898645129086419005581478531225410333382080586421033789193780910018953718151035, 50393070404564103463296427550054748563006296808429533035189599904781417312773992077313879494620891573985025995990362427046, 50560755469108181779253550796419467453822732550048232352976900111320965423447982234319500734441881533078267198679716868147, 31053815510012537761453651023722475580313185793416028968397170841473474014991733203479964389038612632474500092627946654800, 17591111664218390646540290263322438565991600566612830815563803378636955143566240425026196468583694483059211272195601294477, 21986271608940066046025405157876742039438296612428439621847177171849082369085841042738511897780901916375329515475468255050, 48034974317159155266039512640595298551952215288310340780274357988334207990708333015669498846106562573801769307770254498719, 36004675831153886403936901946945223182376387792379251578563086664939536128564846737722629982722249147716340130788282945954, 25073306668918940010167684618611275041628391430411769959226328074664670688685191087925351978453748613698597717497861346474, 47469522007147549577221260501117452889420161959722717283742523186865006152915854789477010249718721160530837181537361829521, 41891935134191484796016413205979896981074425551194362037778585019693019992030844397960200283229977001772348405208697700309, 36386372600251449288495710440082322295559461723712993940948715847660372074073760992208866001633520363080646262787933903319, 29317212004283478670307057049121747821157356830358076566443113892431638436943343021021157473224740231790844713718767067101, 21886686267763551366850327615420094618204739576842569008517234610487301080404816796283498219466272199508410674824388040616, 20411616429357779732793952120212825119292889187817657324394342285965345393312750668668063044583374788264814362683506227263, 53485493262843658089882759154377406167778761476189476207624240342852281822261379986466322017093268857844105466313283823774, 35161703042981482088228959097108586983849134734515301825611227285760422365330968935888437291612114032652294106056829860176, 49041244092941384629503940760863482116972857047549456757616835964853038271098711432865566302116451460152269939117740057593, 31841864808403717042432983181047885467783962186373075159516392266166433086716637660350827586825891142289947420329904397172, 14873397763965609230542160625362991895482690326594922307480948955371485561630013298311219623240481876484895122454113843300, 18755079546695641234254327109303965464905563355656591592515803329191098874367738498377318834760947965509194397144572374577, 48159590525687264056408255917249184247320279026840747880728857996047984794382109903758476645530380992955421151010705361233, 13696433901912863569715585620845682472394721015933569937855873093624441686849856868746673692555192411531595385072763066976, 43320902403606357036982905703763521449172633179735247185797458051230426330315607880436541814545173301238408859251773255451, 44883328646162685531058753390292082144083162945068689613838197042637885098741337621596460084257994429426933464335093779328, 31294638574091737659605854947772659222294270740226223633446769986706942596097634583709348629396671918853616232134150377415, 8632785800688087784188986361808984763246590115202389018828680238402338542959330951828710664987563680467024075096543541894, 9440687306515579204340765250381212998995542938399316347145352808850526843584913908461085482621212648425242170705250976473, 22055192243575904548117693067859137230859459284897513864929867456074778216946933420190144673326915473483280207002480248524, 36662256253439928566474754448626000795159774467206452878102281057086452269711977669589200999159678382386938520261915826572, 43534743115503358911335052278830519629466066620025308640055027020884055331535264596804530826510200771328990442203824809588, 49876198109245109588927811843768268915518612551357890802422138704753641721397914661257895026971287029789081192086230843920, 23354903974148749592917602089310872349463272210477701964802462432883907353202178071167857482270837136785700642169601441293, 24235396818783083317684698571616840837442393440917930990071809125309451834848883941113360083969773773133587532949651716816, 51094354782951038576756399716265129760176221490828533066126314025454263631388307898915176976397302901276114314442460068922, 25739441338390059617103294927516010710186475729160704488952673143395953383460149721243433950367182259995055078242040837465, 54589806361093209402779098389473263397993442808224363579809015671485210049016249978379542820809236402280193729208487997318, 49377881825104725713748459802371358149166706091849232627767090936010790193632435209317051192856519926400090852246409590862]]
p3 = int(1227678060386418065400995844771942486039536259441739)
p2 = int(331662963504457731810383150499096488683)L = matrix(ZZ, 50, 50)
blance = 190for i in range(1, 50):L[i, i] = -out[0]L[0, i] = out[i]
L[0, 0] = 2 ** blanceL = L.LLL()
print(L[0][0] // (2 ** blance))r0 = 204438748210953536814889124338401631787637829938382970084
r0 = int(r0)
# 2 ** 24 --> 三個字節爆破的范圍
for x in range(2 ** 24):term = pow(p2, x, p3) * ord('L')tmp = out[0] - (term % p3)if isinstance(tmp, int) and tmp % r0 == 0:print('find')print(tmp // r0)breakp1 = 35037827049545679985185418677270760927345467737869757739269195663
print(isPrime(p1))text = "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof."[:50]
flag = b''for i in range(len(out)):for x in range(2 ** 24):char_ord = ord(text[i])term = pow(p2, x, p3) * char_ordtmp = out[i] - (term % p3)if isinstance(tmp, int) and tmp % p1 == 0:flag += long_to_bytes(x)breakprint(flag)
攻擊測試成功。
exp
from Crypto.Util.number import *
from sage.all import *# 將out列表中的元素轉換為Python整數
out = [int(n) for n in [55955689617167067845142272755948609874963656354013283213909138253188784455664289394209599504893194046815479435613133872482, 51738951106985534789582800156873064214447115009141851395358593398680065449418642000858582993175014765974322233025402560468, 43573945319843829821920725184088281547305532489519751451499763800628422799013032701490181419765806469391860485141053662596, 34895876359976112314968675364620395223484265572640178454914327558714401687969480967043403862577945400921447020630752198624, 51555436782844906298888846669797960604854519716736863618167845066663375116260279755697529668394648830352544331324161060744, 55744141003892054776121525747018583813791117624865650902927443502780667387453206334771055869042066616611619487656706382335, 34367699515578021632713879600646486701739834667418777229821659379599847551154785907912385034273680138520731840475272705737, 44339810399792345113656941330956116995263700429485813044345754891862149618651963265771201696200701964130843279684938567616, 34326570497877560958872747135365824734807437123704828559398774705565413750541894759277963393365133225475083926966337425343, 42626095253998213899556674112235354585754517085751649324258335650058004667827184269646490282489988318574545679432894265605, 42415450014480995366927416952888288021658081414635630795158687399679183199647126736074376499787788593409159095012846812743, 53333311061471999300029883210769271998536224536553489578657469918556639997822984844922054136242471418016723774153106720708, 42517588289509261713158812398469695762205653369875634690647088002557877122868817096015116143883715881041968697119767653487, 34727065606689887221126275917306570352167760230491529529908178196490374014535669067020081115156984469245551738866332330494, 53247955984141205420676608971982722032749943336041236585832888909499409706807228341704188294406208100432431126181377790862, 40572194875662624610041417759832085492749115909298584978947839576975654926376870126021081958590874647697614820638473243740, 45503700684427371585747323703719900462202772176597057117914117373252576488300789793606879946018350148570048668997073889501, 34053265287706788574908000128783385803465580876366749032974815058317353732949162350582918841267797207951555025066734487889, 48292192485908068458287543859539640698882121660046585646083548770763399328527931028345872887284233928793008384453296471975, 55076628925528633412139088657991745346832636993186245010259996286275952634335237671782417225705350978823831225420996740439, 43137752356796147483320823158663204237107557995169678928247427820594076790702251022160733927505567343922367071441360720199, 60893372277828778488801720386167808454264444985587685427476887749545910124545719108574896204558075550999268680596302479123, 52103327502931101279956694836846451174049281225748847114987045791265959309730714862912017007580046034463662765008441909181, 30869692401700129633955659940641853607978770542368642236872439002070294029225482848854218161120037949741595677084863033537, 58792507825156833153142079944085211896999808416790576546935473108147444560937433726345275222743852156005707061424701746785, 60471707547204679766407040845106011172036992520869354810447905795951236471116518034137557833899524699404943818591463199697, 46044239526264459500973950314432120777471938329374443792499236819017474598545816038734779265357561052409381025198874500449, 40411747929954022622692750029355107300606787811663042177929206061679348315935420775580007408545832456362036261185796116028, 32984800770785295549313032854447741747568767869449825025792141750911724157358032000141074821709579406378281622095331376812, 50022205956054335174309669249186209528589154874997907897932080101367044193005318093036802379233724289717945492331087172161, 54581691642206243068382622033524425912355449682799888573337110347612992464898315158149313824016923538486293571961706361615, 48226514866258517821095752041478478582463549471026551691151963897096768309970796823957477667755310996896561557501641793415, 52714951392349530828438040663251541970279062731559172373715430196853927403594354053118030969773002269953231925072046013747, 46543504750368097245823356781717953683376996100654296460316964982901341570506916691567762592999794113332594693864307022262, 49861510239412789192555065684878847216152518343498445221073025122566189799666974002035535017561355433056721497691241189678, 59714896345367651303559438539037946380765340307511384559307755250140019382872136695857218222382902511424464559566125304432, 40289036404281401073265322883464197930284904991796594124550322301768816174106596534574762004117251730293478504009392345215, 47481288513720056892336818848398114622232351862614424034588214129714755004914356152158980292603552798430410054138503714278, 50969730903840811590944230029568361842531644017273127268213685286314239738315516588333605675948203377693338176600427921136, 37548905947197913866264833631819373169029940466940632819412976864383350809109404084413566498096632532601884180314086997288, 42019418538744107546948356120011039004209841362240272875975997829726699743056732891345506420020947943050699372280516980752, 34205339219413048285363667318099130479172627076468433337007958281208463378476269016098142665722841002290437933016360930841, 56872799693035098542949228439850575084667345852204036956901127528130709397540074159480144298935825359391280634774662609518, 50660315555546380137356709626968732651298644584802556110992260827459536648983890551407485072002154688975509763701723358140, 52706740898177785145763124739620609162017784550550753415550071383671207591371329881622950877349279449546204338601216527048, 47734317400836557124228704924423846354998521266996367170286928207251026236455511271301995232391908218154855495412436597910, 44595804948726078571879879904129087265908543989415176021586186760051432388686628837635320448149402811619783579770888899534, 52035239770773753885902477138321968048817894438466385394554311396683044231957140269193226573087366655737118158344592420370, 59732908795784994749040504187349830554429844653686789856734106808946166419631042790416100791281608847924286907319915106879, 47610136912584873107308412594922250411084715104960696288012806673514928251307784777614656561875366192759291230021161752295]]p3 = int(749950024507589444154899655275603865985544701307377)
p2 = int(280347458852017131306028610784029566433)L = matrix(ZZ, 50, 50)
blance = 190for i in range(1, 50):L[i, i] = -out[0]L[0, i] = out[i]
L[0, 0] = 2 ** blanceL = L.LLL()
print(L[0][0] // (2 ** blance))r0 = 1441906278903284351785075298020007088103701774963116481351
r0 = int(r0)for x in range(2 ** 24):term = pow(p2, x, p3) * ord('L')tmp = out[0] - (term % p3)if isinstance(tmp, int) and tmp % r0 == 0:print('find')print(tmp // r0)breakp1 = 38806745234320660979374953867342893674803158280994180937455767551
print(isPrime(p1))text = "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof."[:50]
flag = b''for i in range(len(out)):for x in range(2 ** 24):char_ord = ord(text[i])term = pow(p2, x, p3) * char_ordtmp = out[i] - (term % p3)if isinstance(tmp, int) and tmp % p1 == 0:flag += long_to_bytes(x)breakprint(flag)# flag{8dce731a55932d083733135e8c2b269102620bb754cbd}
的小項目部署記錄)
