# AIS3 2023 crypto writeup
因為其他類型題目我解的也不多，所以這裡就只紀錄crypto的題目
## Fernet
:::spoiler chal.py
```python
import os
import base64
from cryptography.fernet import Fernet
from Crypto.Hash import SHA256
from Crypto.Protocol.KDF import PBKDF2
from secret import FLAG
def encrypt(plaintext, password):
salt = os.urandom(16)
key = PBKDF2(password.encode(), salt, 32, count=1000, hmac_hash_module=SHA256)
f = Fernet(base64.urlsafe_b64encode(key))
ciphertext = f.encrypt(plaintext.encode())
return base64.b64encode(salt + ciphertext).decode()
# Usage:
leak_password = 'mysecretpassword'
plaintext = FLAG
# Encrypt
ciphertext = encrypt(plaintext, leak_password)
print("Encrypted data:",ciphertext)
```
:::
:::spoiler output
```
Encrypted data: iAkZMT9sfXIjD3yIpw0ldGdBQUFBQUJrVzAwb0pUTUdFbzJYeU0tTGQ4OUUzQXZhaU9HMmlOaC1PcnFqRUIzX0xtZXg0MTh1TXFNYjBLXzVBOVA3a0FaenZqOU1sNGhBcHR3Z21RTTdmN1dQUkcxZ1JaOGZLQ0E0WmVMSjZQTXN3Z252VWRtdXlaVW1fZ0pzV0xsaUM5VjR1ZHdj
```
:::
<br/>
上網查發現Fernet是一個對稱式加密，key也都給了，就查一下解密如何實作就好
:::spoiler sol.py
```python
import os
import base64
from cryptography.fernet import Fernet
from Crypto.Hash import SHA256
from Crypto.Protocol.KDF import PBKDF2
from base64 import b64decode
data='iAkZMT9sfXIjD3yIpw0ldGdBQUFBQUJrVzAwb0pUTUdFbzJYeU0tTGQ4OUUzQXZhaU9HMmlOaC1PcnFqRUIzX0xtZXg0MTh1TXFNYjBLXzVBOVA3a0FaenZqOU1sNGhBcHR3Z21RTTdmN1dQUkcxZ1JaOGZLQ0E0WmVMSjZQTXN3Z252VWRtdXlaVW1fZ0pzV0xsaUM5VjR1ZHdj'
salt=b64decode(data)[:16]
cipher=b64decode(data)[16:]
#print(salt,cipher)
leak_password ='mysecretpassword'
key = PBKDF2(leak_password.encode(), salt, 32, count=1000, hmac_hash_module=SHA256)
f = Fernet(base64.urlsafe_b64encode(key))
plaintext=f.decrypt(cipher)
print(plaintext)
#FLAG{W3lc0m3_t0_th3_CTF_W0rld_!!_!!!_!}
```
:::
## 2DES
::: spoiler main.js
```javascript
const crypto = require('crypto')
const FLAG = require('./flag')
const assert = require('assert')
// Generate key and IV
const key1 = crypto.randomBytes(8)
const key2 = crypto.randomBytes(8)
const iv = Buffer.concat([Buffer.from('AIS3 三')])
for (let i = 0; i < 8; i++) {
key1[i] = key1[i] | 0b11110000
key2[i] = key2[i] | 0b11110000
}
function encrypt(msg, key, iv) {
const cipher = crypto.createCipheriv('des-cbc', key, iv)
let encrypted = cipher.update(msg)
encrypted = Buffer.concat([encrypted, cipher.final()])
return encrypted
}
function decrypt(msg, key, iv) {
const decipher = crypto.createDecipheriv('des-cbc', key, iv)
let decrypted = decipher.update(msg, 'nyan~')
decrypted = Buffer.concat([decrypted, decipher.final()])
return decrypted
}
const hint_pt = Buffer.from('AIS3{??????????}', 'utf8')
res = encrypt(encrypt(FLAG, key1, iv), key2, iv)
hint = encrypt(encrypt(hint_pt, key1, iv), key2, iv)
assert.equal(
decrypt(decrypt(res, key2, iv), key1, iv).toString('utf8'),
FLAG.toString('utf8')
)
console.log(`let res = '${res.toString('hex')}'`)
console.log(`let hint_pt = '${hint_pt.toString('hex')}'`)
console.log(`let hint = '${hint.toString('hex')}'`)
// console.log(`let key1 = '${key1.toString('hex')}'`)
// console.log(`let key2 = '${key2.toString('hex')}'`)
console.log(`let iv = '${iv.toString('hex')}'`)
console.log(`
module.exports = {
res: res,
hint: hint,
iv: iv,
hint_pt: hint_pt,
}
`)
```
:::
::: spoiler output.js
``` javascript
let res = '6020e9735ca3bf2f63aebcf3622c994880ffed2b509c91414c75d4c500ee80f4'
let hint_pt = '414953337b3f3f3f3f3f3f3f3f3f3f7d'
let hint = '118cd68957ac93b269335416afda70e6d79ad65a09b0c0c6c50917e0cee18c93'
let iv = '4149533320e4b889'
module.exports = {
res: res,
hint: hint,
iv: iv,
hint_pt: hint_pt,
}
```
:::
<br/>
一開始看到這題是javascript寫的想直接跳過= =
由於我不會js只好請強大的ChatGPT翻譯成python
:::spoiler ChatGPT.py
```python
import random
from Crypto.Cipher import DES
FLAG = b'firstctf'
key1 = bytes([random.getrandbits(8) | 0b11110000 for _ in range(8)])
key2 = bytes([random.getrandbits(8) | 0b11110000 for _ in range(8)])
iv = 'AIS3 三'.encode('utf-8')
def encrypt(msg, key, iv):
cipher = DES.new(key, DES.MODE_CBC, iv)
encrypted = cipher.encrypt(msg)
return encrypted
def decrypt(msg, key, iv):
decipher = DES.new(key, DES.MODE_CBC, iv)
decrypted = decipher.decrypt(msg)
return decrypted
hint_pt = b'AIS3{??????????}'
res = encrypt(encrypt(FLAG, key1, iv), key2, iv)
hint = encrypt(encrypt(hint_pt, key1, iv), key2, iv)
assert decrypt(decrypt(res, key2, iv), key1, iv).decode('utf-8') == FLAG.decode('utf-8')
print(f"res = '{res.hex()}'")
print(f"hint_pt = '{hint_pt.hex()}'")
print(f"hint = '{hint.hex()}'")
print(f"key1 = '{key1.hex()}'")
print(f"key2 = '{key2.hex()}'")
print(f"iv = '{iv.hex()}'")
print("""
module.exports = {
'res': res,
'hint': hint,
'iv': iv,
'hint_pt': hint_pt,
}
""")
```
:::
<br/>
不論是聽過密碼學的課或者是玩過picoCTF的其中一題"Double DES"，看到2DES自然而然就會反射動作想到**meet in the middle attack**
但這題似乎仍有蹊蹺，觀察產生key1和key2的形式，會發現key每個byte的開頭都必然是1111
再者靈光一現想起DES有一個特殊(莫名其妙)的性質，每個byte的最後一個bit作為檢查碼是不重要的
綜合以上三點就可以寫出爆搜key的程式啦~
另外我一開始是把hint解出來的東西直接完全去和hint_pt比對，然後想說怎麼找不到key，後來才發現hint和hint_pt的byte數對不上，大概是因為padding的原因，因此記得比對前16個bytes就好
:::spoiler sol.py
```python
import random
from Crypto.Cipher import DES
res = bytes.fromhex('6020e9735ca3bf2f63aebcf3622c994880ffed2b509c91414c75d4c500ee80f4')
hint_pt = bytes.fromhex('414953337b3f3f3f3f3f3f3f3f3f3f7d')
hint = bytes.fromhex('118cd68957ac93b269335416afda70e6d79ad65a09b0c0c6c50917e0cee18c93')
iv = bytes.fromhex('4149533320e4b889')
def encrypt(msg, key, iv):
cipher = DES.new(key, DES.MODE_CBC, iv)
encrypted = cipher.encrypt(msg)
return encrypted
def decrypt(msg, key, iv):
decipher = DES.new(key, DES.MODE_CBC, iv)
decrypted = decipher.decrypt(msg)
return decrypted
key_test=[]
for i1 in range(0,16,2):
for i2 in range(0,16,2):
for i3 in range(0,16,2):
for i4 in range(0,16,2):
for i5 in range(0,16,2):
for i6 in range(0,16,2):
for i7 in range(0,16,2):
for i8 in range(0,16,2):
key_test.append(bytes([i1+240,i2+240,i3+240,i4+240,i5+240,i6+240,i7+240,i8+240]))
table={}
#count=0
for i in key_test:
ct = encrypt(hint_pt, i, iv)
table[ct] = i
'''count+=1
if(count%100000==0):
print(count)'''
#count=0
for i in key_test:
ct = decrypt(hint, i, iv)[:16]
'''count+=1
if(count%100000==0):
print(count)'''
if ct in table:
key1=table[ct]
key2=i
print(key1,key2)
break
flag=decrypt(decrypt(res, key2, iv), key1, iv)
print(flag[:18].decode())
#AIS3{折半枚舉}
```
:::
## MSB
nc chals1.ais3.org 12347(需進行連線)
:::spoiler chal.py
``` python
import os
import random
from Crypto.Util.number import getPrime
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
print(f'Your key: {hex(n)} {hex(e)}')
secret = random.randrange(n)
hint = pow(secret, e, n)
print(f'Your hint: {hex(hint)}')
for _ in range(1500):
ct = int(input('The ciphertext? '), 16)
if ct == 0:
break
pt = pow(ct, d, n)
if pt > n // 2:
print('Your plaintext is big')
else:
print('Your plaintext is small')
if input('The secret? ') == hex(secret):
flag = os.environ['FLAG']
print(f'Your flag: {flag}')
else:
print('No flag')
```
:::
<br/>
看到這題應該會自然想到RSA的經典題型LSB oracle，於是解題的方法也相差不遠，但我想實作的方法還是想了好久...
大意就是讓ct(密文) * pow(2,e,n)，解出來的明文就會是pt * 2，ct(密文) * pow(2,e,n) * pow(2,e,n)，解出來的明文就會是pt * 4，依此類推
- 假設一開始解出pt回傳small的話，就代表0 < pt < n/2
- 若解出來pt * 2回傳small，則代表0 < pt <n/4
- 解出來pt * 4...
- 若解出來pt * 2回傳big，則代表n/4 < pt < n/2
- 解出來pt * 4...
- 假設一開始解出pt回傳big的話，就代表n/2 < pt < n/4
- 若解出來pt * 2回傳small，則代表n/2 < pt < 3n/4
- 解出來pt * 4...
- 若解出來pt * 2回傳big，則代表3n/4 < pt < n
- 解出來pt * 4...
藉由這樣子的方法，我們可以一直將pt的範圍縮小，最後這個範圍只包含一個整數就知道是pt了
:::spoiler sol.py
```python
from pwn import *
r=remote('chals1.ais3.org' ,12347)
n=int(r.recvline().split()[2].decode()[2:],16)
hint=int(r.recvline().split()[2].decode()[2:],16)
e=65537
print(n,hint)
ct=hint
assist=pow(2,e,n)
lower_bound=0
upper_bound=1
for i in range(1500):
r.sendlineafter(b'? ',hex(ct))
if r.recvline().split()[3]==b'big': #表示在原本的右邊
#print('big')
upper_bound=upper_bound*2
lower_bound=lower_bound*2+1
else: #表示在原本的左邊
#print('small')
upper_bound=upper_bound*2-1
lower_bound=lower_bound*2
ct*=assist
ct%=n
#print(f'lower_bound{lower_bound}\nupper_bound{upper_bound}')
#print(n*upper_bound//(2**1500))
r.sendlineafter(b'? ',hex(n*upper_bound//(2**1500)))
print(r.recvline())
print(r.recvline())
# AIS3{O0o0oO0o0oOooooO0o0oOOO0oO0o0o_Y0u_a43_4_tru1ly_Or4c13!!@#!@#!@#!@$!@$!@}
```
:::
## ecc
:::spoiler chal.py
``` python
from fastecdsa.curve import secp256k1
from fastecdsa.keys import gen_keypair
from hashlib import sha256
from itertools import count
from secrets import randbelow
def encrypt(pk, pt, nonce):
s = nonce * pk
c1 = s.x * pt % secp256k1.p
c2 = nonce * secp256k1.G
return c1, c2
def decrypt(sk, ct):
c1, c2 = ct
s = sk * c2
pt = c1 * pow(s.x, -1, secp256k1.p) % secp256k1.p
return pt
if __name__ == "__main__":
sk, pk = gen_keypair(secp256k1)
ct = encrypt(pk, 1234, 5678)
assert decrypt(sk, ct) == 1234
gen = count(randbelow(secp256k1.q), randbelow(secp256k1.q))
secret = open("flag.txt", "rb").read().strip()
ciphertext = [encrypt(pk, x, y) for x, y in zip(secret, gen)]
print([(c1, c2.x, c2.y) for c1, c2 in ciphertext])
```
:::
:::spoiler output
```
[(92250300798133079030583415814570300169682735045667413833813739690055913621327, 6177650748878642258471251377128240618321809005857813396671856838737682682263, 4040982410587784601326454129519843142910998352441298365778860192773551335290), (28560660160093777918254370191521599173518452600710608242023985866786513743852, 113543165954701601091120165874224816076876612096466723839609035126452140111209, 89592798696873400968441277053088777404312258478197943430395498191266378297769), (13113141307887511512842228713795601133568074220626462886066541768452844625760, 51618993719439367643025525397412916968808056837334913281157723017379362145231, 76937947952747228024411800460809747092738833902437310662031309521358036269486), (65168823803043635444376250690635825778120951289249146498078212145434118052901, 40506687365392879517922145395454726380394301676126116435934646071814853407085, 43972782345726607483308731148185866257918674613348123410412418999642125331269), (27352490856272895838467579815818464060589016760884120705067475734868520754344, 5486439789022084684250875775170412116598994498177322654395867191506555245431, 15051562112672004346073257634238899364653153189753656808710385213911869823629), (30488097974888975809584258906186425894233872155686427092092119952091222709200, 9454788602337364837927367130873265848351038267002005471002237445711256068747, 58733954046584672344362181386062471992546938605424347097823126601345873953681), (105546164962660839114522082854939355020267196606220293597368603112140581633785, 57144614081617802370699141489106775215233908899477373349013875527109600163091, 41362652668902415036166841994754527923155572878571834233659888163611334725858), (59746687509889087129729919045298337982903113294294879207852118325973729095737, 44473315139130013415987668085753430108313272195310680954160418403068559316041, 94431154260384877735075372167679862595716702151558699418684692157848435458202), (9992740461843789178858910394968359176712565474459946478698267684893035541628, 53067302540814368122404839028037815740543937544521019379430507621780169278231, 27038065217322914336860820103442524247398334288846298989691794369489738590277), (99247572379891121160506356011364772788033431535592436696621518128845019173448, 94131594482550337643209515020711902372165243656905286192028497903229101398045, 82145751642237020671941115770396600722120194279185851628683498713254827095860), (9035139304347161333869867816172492463646515423210247681301127370991908653283, 81782495739614062451314562322434671664877477988398584109508604296527033072327, 52945384870016037960929874727004289202692054826153845649813201801513245633006), (71469425546604143301185702174101913867821305053386772569048132140568117867661, 113800997911141610783044313033225544205265591255471239538249188865135938057464, 113250510423905479296441830974812979178830158697924372331469897384146380171517), (27279648104940774395896331097297763891468729889191277672655701937136170514430, 99925662036186894403037644742007285039451039474349420833233063668507017934012, 75963691217135453814359090834423173564291273235566142225489233685056915060673), (107359056967215779261148086875631123315046374883316032892218220706593891613729, 104307330349836682343147436102373379586335134444941300214104219446844504163385, 77105876351477475421005087290340863705755822994098826740363656336010430877707), (78642807780393034825043037298182905984345611477734449632968041088332654611395, 73195591790982358829302285194336852820724562529430565067540703265938721412128, 63386096605638866611507701623452235827608688381534852957884158756256867555404), (72261347091829369959114974679579173407016020883431781785712794081317400271148, 2248803898767268655151391227608426993678453311719205652104131523899360720822, 27651857109207572533491645188230631326696773321690864774617072392739230849544), (29464840757433151276199971239796060033443769672025662466180649278147664499523, 100181931280679766957864749238470515826165909628418881344682904206169453114476, 31260797548179729929521252431077256474085366843228791254431342359044953765365), (16823335848446921803515673432797774196245316359126934985561962235946429847909, 74482009434502832747012725342203169809510353899689482625671496476311235131405, 72365535588761297295530785817397576329248498455372041849806239806389511277683), (97006794100090130518349437539553303437786826994570625567440563216181213948361, 108462109925026062437913600840926111057312665672000940885164172225307000547582, 63467173365476848484458474933447146996830311104010047594184724983230035030243), (42252290693036479663943042337042715437482845968162707519936222851604210918785, 48967245471915084673001564435170801295625933255864035548652113128348318769007, 46974950861940267630637000266084033840961263308269838814643578963914500296719), (5589395015140132254820244521881520707445525310691119828960639289102254410244, 115668781843661709011919287711112546255102294186265065488684915610131174014110, 78452622369227140534010959804281180432217669384318068622929510248160855800692), (100594659294586377215635846597823433470191724028032289783832685811157656361429, 5120491391028426498962413365942992951235170979518581764606149450274747804224, 89872685077773877311081115039055484025624202551267984153160519164544821447583), (21158873068444899332848106845697881895939045412424001827214332955190087523590, 65023475455104294387809989718584040694417241287259718772846858129907635174379, 75344225816427914032106383502385505342296165623914707251683752505506039077574), (9371294287280608666561351797660446791517996564056768525856189327932302732486, 106633558435451952041936015362488611462258522818945212073074802647091285048529, 36976103993273797975523114938348137783307891717323844265399509305626193550792), (53381256726790101535069378763214667034490159334831263555816393335184605227842, 87766490230923938771797468996992604021881383125462303823055241941112107981216, 31613414278053282577049703439627518233969359678144979194709625427143695079536), (103993373385377537364158988280318988138408006730023626442493540589088244100321, 105991841102300500615947815565027898764961538988374930957422116246949201432433, 80690522548068509960751555587159392641235529005841347407463026472832649385178), (108579420120478326904724494993704579530652761621815523574891395725141414188542, 25596553623830574090370100579043083288319479333561749629912419233434387449852, 53343972089593791872208427510953251518495652004829891269788817450147333507516), (67885912212777624949247713814050449550601689631942320212616444305463114200639, 43184725698161480310097941643973831341474700098319664427247212728255401908845, 103634233387879880407309291137361848116362630036304489516535605923686402462712), (97411234349818120240551472898203005242395442334741368576883223709977898617665, 73465733755127376404877485546668685272458927031109390640571376008925430888538, 32087809928071698417815263330104471699666302422663129523499651815220326634379), (98636681579821638340488466398599345935487413676448951943432737152441483103082, 95556601299350165462884451520773920244674412895136131635066772586049506172639, 92350424386393756721054915191370416757212113515827745905265170580485575927468), (50812275658313133170786136420323697154692590168799809547877499040492996650196, 47995650294962748643337258368013096355913561559642697280676328504751268832906, 44835755230631031804560494792549227010426389445114492987235797897716962884749), (9279715121468590125122612630858040675364522238304586264024275151989716058104, 48260327499277631118671629587363689885116537448437685025399229779458555405455, 15819670094984216070328502618428653811841161527134907686283129535436293657631), (72851624216642123617856663956592457151943211152892028887708261494769588599444, 111340714014915731173779024515519911925173578595521078593473238817752165924388, 10160898516041411136446849459767417275284908977429496818779240958946507063640), (1126330502272149343863226985772202008193068379465024093985319652218538850617, 52692577549449290343958271182206586429092710930069720800268566873812680106524, 11519751236757887505723583908747843560588479601225414226997797353857429691417), (88957777808621869446502156523982859169285791063936875651400734930013133764861, 16437407087693310849139438948889564249598135147652562302468373152025838253431, 107858945994628891244350840992627182445778912642134887877435620917851926564825), (110877365449685321610691753508864657004247860236859187415515100948336408992490, 39136797977397083868971864229075979060814481900601662628373430700799548558565, 92418529861729436049748977893597537510365313009343648284723500165815894709679), (20713760715345293552792113302845394830102910653242006677437722881257506307311, 68198671384688543239257859971713482936908309807104706754387820596896398581797, 111177303358221592783047898878739465300784988169412278847069622691289821171619), (114930384587018937068360542114268399904327959769113973721794141293337403231724, 20279137456763956185799576388090643533646627254587196397575626880249808045931, 69983586299533755160137600359759212605514239782112782815452409270316999829240), (111221496302185435489016817725253504311088463577011956993216969736810327630016, 39404171394716709093225433998544333771077953087343275331055561656629457618280, 60919410606849533655035953671781937215911541856213725366423200082010744428899), (87552047718051817187473003736110163360149578328878819145806055060395533933875, 61544362144710648259478245088745688574903752982213766191928700271552631426842, 114320010625873032581448568627922846005306200637762981046843377960526293635722), (82765298108340216863311408216130211438189943912676022780181930987462994084329, 63924478342827487522808269503940449067983349165209783152447299612795674372151, 46818358529303379621569325054817010740424846746274913305187392050719313315481), (90171620415951962157779564046419969607292911819395030771605353683418885281871, 27670802218278931096958126135314461394196745331241049624397161752847765079867, 112696042502515883366784096242185043972999774821795801610799036441130729828003), (100214161501844990638677348202026144722359539245509589942993992538119094046668, 63962510947828966930565442088426709499034895713977934816300424457848317805862, 18884104353417093470136901635127113940033626538677125384705917638025675714188), (104685109449502104243375356952715109150932540986689358550872415152203555081628, 52682461071968037404045898332914854020234158186183511446566808961596092921637, 113240920021182779457959967234864734236344278520604524089502403178879673606376), (25375741261572723556579397056123939612822632953733398967954802995210767116166, 109091893555309291430933407887392019328056220336914835074665572951469289242157, 90670110792221883996187348700910505681055885477583801408216371226321383082250), (58913256253676878754396772542901058062960739663136672404546218247449955826217, 20476564629519912554045551156054534252670243530526366267884763394482378534287, 43414823558829941459518056527757595345840072122983073739673542488355003785841), (46040503169738671751530280410111756133907287025285732732574646137963898141988, 90038056418055734858233437196561375254873922262665809840608584394489489488219, 52933398566171228428832264505494512086280859410607955234187740679394717003399), (28322564428919492359306157284433228300356912746732283837537184194533070237766, 29160467048185357196899930057099189267580745093622340902659224762309346441214, 26039353134960195170402725279915206394821006686551445832909398074040986084393), (21643642884629372272239257427422434548111071093660016278189319354746988561854, 31263703152705262059536262874656994231536759730561154000449259645368999614764, 105199911349953969667322391118024811020759893123322744450402807102305795159656), (17818375562293210038262569309183431887963616759999164580166459150501562617240, 68709256128099365266791269949117656541683814615625054357862706510892141820878, 68724054513434230732552584911267956250473279585997303572350834208281517688952), (46488526841099552357136658607903610694782584037592204410271971080242497794732, 22280500700029517773383356695696521166361037102529337184897270945540264449488, 106292352202686575557293412717711544291717306594663944198885951077838844230369), (54744569834148748314048978355810647449424503046831552654972076945301737753969, 48598390636071123210548071853272745940731272896777472602381115938455819430802, 110544654813559881208673688219066901740865112556773737149166411878048092007437), (24183091442912524185282519629523932263130931897426402483950594474383857495607, 5086141929975221005656275781445468353799317960140742705329752065204981608145, 100620023044695585644613898936667010326684864572598750259111889731381322340813), (42330455466109742508341894104599280563559287463495821517968429639532359134645, 44924292261952319230418369007369099808082554564871599897592332746013706876704, 70240693395219791641744304573139966488195299647643970164049020659518103179565), (30873674199588312263280989051400695503893758434809750722095730459397008129773, 85687002887482648966286365632763020770625783090855626646288044318704061992398, 38726798613999661261482133360696273360000894413997363296350489598487671807066), (21061375475266480827111086341362443323761389847974735186232979950366078780948, 39345717478281582081752146099293508209186164995099295942813427978917315121612, 4303145176331772274895356697847071390007962769186330891973397374076733831296), (71836515914263137511603033075549707493733097404841325965271406670598051657327, 104949187941865258401710485744737529239458053528810734579776526613256694871588, 46223863810961260605992460270292523432227620490423799813336984029067836931192), (6472181066670151865554687923655274239762670007453239076966086444665009736030, 103657301219312567282166288851937146835288762663288436493406315716582028486335, 23179060229166391936525616790300430138190433638538633937789307644830182202927), (3943075870713949956934984379358132766737763685211205508940763607803387515516, 107144890290963493355297407104644158131965088413544131077537151546644680403374, 110153338056816978556099947913991403004622678694996339328972823398253788963842), (38007566370567363886822508728851512337177336192994339535634073334921123145994, 1718451956071296497063951710564547470677098410718606622164542924310855741230, 21020493579482316538469623244523156826281830248580934928123544005081719293439), (71754547479175731957497895770747906319812332631655894216392250210975293654232, 6436425397057539899435653899833442604312362194787080233245347001285245501781, 6419993035939720501315696960534652280763998311652227591015061863949621803973), (76558620918351656697448366721801622034549874825557870604565139745117540417504, 22271382621497156322785007861677625630147677406263147631868575192142852890723, 69861632402326050501115368835886284065019324782781202826916046056889007431368)]
```
:::
<br/>
這題的重點應該是使用了count這個函數，上網查一下count的用法就會發現count(start, step)會產生start, start+step, start+2*step, ...，也就是加密使用的nonce是線性的，這大有問題
因此加密的過程可以寫成
```c1(第一個字元)=(start * pk).x * pt % secp256k1.p``` (pk為橢圓曲線上的一個點)
```
c1(第二個字元)=((start + step) * pk).x * pt % secp256k1.p
=((start * pk + step * pk).x % secp256k1.p
```
```
c1(第三個字元)=((start + 2*step) * pk).x * pt % secp256k1.p
=((start * pk + 2 * step * pk).x % secp256k1.p
```
...
由於c1都知道，明文的開頭是```AIS3{```知道，故移項之後就可以回推出start * pk和step * pk這兩點了，有了這兩點之後就可以無痛解出明文了
我自己一開始是用E1=ecc.lift_x(x1), E2=ecc.lift_x(x2), E3=ecc.lift_x(x3)，然後就想說E3-E2為什麼和E2-E1不一樣，難道是我哪裡想錯了嗎！？但後來才想到橢圓曲線上給定x座標會有兩個點才對，所以記得要加上ecc.lift_x()的參數要加上all=True去找呦！
:::spoiler sol.py(要在sage上跑)
```python
cipher=[(92250300798133079030583415814570300169682735045667413833813739690055913621327, 6177650748878642258471251377128240618321809005857813396671856838737682682263, 4040982410587784601326454129519843142910998352441298365778860192773551335290), (28560660160093777918254370191521599173518452600710608242023985866786513743852, 113543165954701601091120165874224816076876612096466723839609035126452140111209, 89592798696873400968441277053088777404312258478197943430395498191266378297769), (13113141307887511512842228713795601133568074220626462886066541768452844625760, 51618993719439367643025525397412916968808056837334913281157723017379362145231, 76937947952747228024411800460809747092738833902437310662031309521358036269486), (65168823803043635444376250690635825778120951289249146498078212145434118052901, 40506687365392879517922145395454726380394301676126116435934646071814853407085, 43972782345726607483308731148185866257918674613348123410412418999642125331269), (27352490856272895838467579815818464060589016760884120705067475734868520754344, 5486439789022084684250875775170412116598994498177322654395867191506555245431, 15051562112672004346073257634238899364653153189753656808710385213911869823629), (30488097974888975809584258906186425894233872155686427092092119952091222709200, 9454788602337364837927367130873265848351038267002005471002237445711256068747, 58733954046584672344362181386062471992546938605424347097823126601345873953681), (105546164962660839114522082854939355020267196606220293597368603112140581633785, 57144614081617802370699141489106775215233908899477373349013875527109600163091, 41362652668902415036166841994754527923155572878571834233659888163611334725858), (59746687509889087129729919045298337982903113294294879207852118325973729095737, 44473315139130013415987668085753430108313272195310680954160418403068559316041, 94431154260384877735075372167679862595716702151558699418684692157848435458202), (9992740461843789178858910394968359176712565474459946478698267684893035541628, 53067302540814368122404839028037815740543937544521019379430507621780169278231, 27038065217322914336860820103442524247398334288846298989691794369489738590277), (99247572379891121160506356011364772788033431535592436696621518128845019173448, 94131594482550337643209515020711902372165243656905286192028497903229101398045, 82145751642237020671941115770396600722120194279185851628683498713254827095860), (9035139304347161333869867816172492463646515423210247681301127370991908653283, 81782495739614062451314562322434671664877477988398584109508604296527033072327, 52945384870016037960929874727004289202692054826153845649813201801513245633006), (71469425546604143301185702174101913867821305053386772569048132140568117867661, 113800997911141610783044313033225544205265591255471239538249188865135938057464, 113250510423905479296441830974812979178830158697924372331469897384146380171517), (27279648104940774395896331097297763891468729889191277672655701937136170514430, 99925662036186894403037644742007285039451039474349420833233063668507017934012, 75963691217135453814359090834423173564291273235566142225489233685056915060673), (107359056967215779261148086875631123315046374883316032892218220706593891613729, 104307330349836682343147436102373379586335134444941300214104219446844504163385, 77105876351477475421005087290340863705755822994098826740363656336010430877707), (78642807780393034825043037298182905984345611477734449632968041088332654611395, 73195591790982358829302285194336852820724562529430565067540703265938721412128, 63386096605638866611507701623452235827608688381534852957884158756256867555404), (72261347091829369959114974679579173407016020883431781785712794081317400271148, 2248803898767268655151391227608426993678453311719205652104131523899360720822, 27651857109207572533491645188230631326696773321690864774617072392739230849544), (29464840757433151276199971239796060033443769672025662466180649278147664499523, 100181931280679766957864749238470515826165909628418881344682904206169453114476, 31260797548179729929521252431077256474085366843228791254431342359044953765365), (16823335848446921803515673432797774196245316359126934985561962235946429847909, 74482009434502832747012725342203169809510353899689482625671496476311235131405, 72365535588761297295530785817397576329248498455372041849806239806389511277683), (97006794100090130518349437539553303437786826994570625567440563216181213948361, 108462109925026062437913600840926111057312665672000940885164172225307000547582, 63467173365476848484458474933447146996830311104010047594184724983230035030243), (42252290693036479663943042337042715437482845968162707519936222851604210918785, 48967245471915084673001564435170801295625933255864035548652113128348318769007, 46974950861940267630637000266084033840961263308269838814643578963914500296719), (5589395015140132254820244521881520707445525310691119828960639289102254410244, 115668781843661709011919287711112546255102294186265065488684915610131174014110, 78452622369227140534010959804281180432217669384318068622929510248160855800692), (100594659294586377215635846597823433470191724028032289783832685811157656361429, 5120491391028426498962413365942992951235170979518581764606149450274747804224, 89872685077773877311081115039055484025624202551267984153160519164544821447583), (21158873068444899332848106845697881895939045412424001827214332955190087523590, 65023475455104294387809989718584040694417241287259718772846858129907635174379, 75344225816427914032106383502385505342296165623914707251683752505506039077574), (9371294287280608666561351797660446791517996564056768525856189327932302732486, 106633558435451952041936015362488611462258522818945212073074802647091285048529, 36976103993273797975523114938348137783307891717323844265399509305626193550792), (53381256726790101535069378763214667034490159334831263555816393335184605227842, 87766490230923938771797468996992604021881383125462303823055241941112107981216, 31613414278053282577049703439627518233969359678144979194709625427143695079536), (103993373385377537364158988280318988138408006730023626442493540589088244100321, 105991841102300500615947815565027898764961538988374930957422116246949201432433, 80690522548068509960751555587159392641235529005841347407463026472832649385178), (108579420120478326904724494993704579530652761621815523574891395725141414188542, 25596553623830574090370100579043083288319479333561749629912419233434387449852, 53343972089593791872208427510953251518495652004829891269788817450147333507516), (67885912212777624949247713814050449550601689631942320212616444305463114200639, 43184725698161480310097941643973831341474700098319664427247212728255401908845, 103634233387879880407309291137361848116362630036304489516535605923686402462712), (97411234349818120240551472898203005242395442334741368576883223709977898617665, 73465733755127376404877485546668685272458927031109390640571376008925430888538, 32087809928071698417815263330104471699666302422663129523499651815220326634379), (98636681579821638340488466398599345935487413676448951943432737152441483103082, 95556601299350165462884451520773920244674412895136131635066772586049506172639, 92350424386393756721054915191370416757212113515827745905265170580485575927468), (50812275658313133170786136420323697154692590168799809547877499040492996650196, 47995650294962748643337258368013096355913561559642697280676328504751268832906, 44835755230631031804560494792549227010426389445114492987235797897716962884749), (9279715121468590125122612630858040675364522238304586264024275151989716058104, 48260327499277631118671629587363689885116537448437685025399229779458555405455, 15819670094984216070328502618428653811841161527134907686283129535436293657631), (72851624216642123617856663956592457151943211152892028887708261494769588599444, 111340714014915731173779024515519911925173578595521078593473238817752165924388, 10160898516041411136446849459767417275284908977429496818779240958946507063640), (1126330502272149343863226985772202008193068379465024093985319652218538850617, 52692577549449290343958271182206586429092710930069720800268566873812680106524, 11519751236757887505723583908747843560588479601225414226997797353857429691417), (88957777808621869446502156523982859169285791063936875651400734930013133764861, 16437407087693310849139438948889564249598135147652562302468373152025838253431, 107858945994628891244350840992627182445778912642134887877435620917851926564825), (110877365449685321610691753508864657004247860236859187415515100948336408992490, 39136797977397083868971864229075979060814481900601662628373430700799548558565, 92418529861729436049748977893597537510365313009343648284723500165815894709679), (20713760715345293552792113302845394830102910653242006677437722881257506307311, 68198671384688543239257859971713482936908309807104706754387820596896398581797, 111177303358221592783047898878739465300784988169412278847069622691289821171619), (114930384587018937068360542114268399904327959769113973721794141293337403231724, 20279137456763956185799576388090643533646627254587196397575626880249808045931, 69983586299533755160137600359759212605514239782112782815452409270316999829240), (111221496302185435489016817725253504311088463577011956993216969736810327630016, 39404171394716709093225433998544333771077953087343275331055561656629457618280, 60919410606849533655035953671781937215911541856213725366423200082010744428899), (87552047718051817187473003736110163360149578328878819145806055060395533933875, 61544362144710648259478245088745688574903752982213766191928700271552631426842, 114320010625873032581448568627922846005306200637762981046843377960526293635722), (82765298108340216863311408216130211438189943912676022780181930987462994084329, 63924478342827487522808269503940449067983349165209783152447299612795674372151, 46818358529303379621569325054817010740424846746274913305187392050719313315481), (90171620415951962157779564046419969607292911819395030771605353683418885281871, 27670802218278931096958126135314461394196745331241049624397161752847765079867, 112696042502515883366784096242185043972999774821795801610799036441130729828003), (100214161501844990638677348202026144722359539245509589942993992538119094046668, 63962510947828966930565442088426709499034895713977934816300424457848317805862, 18884104353417093470136901635127113940033626538677125384705917638025675714188), (104685109449502104243375356952715109150932540986689358550872415152203555081628, 52682461071968037404045898332914854020234158186183511446566808961596092921637, 113240920021182779457959967234864734236344278520604524089502403178879673606376), (25375741261572723556579397056123939612822632953733398967954802995210767116166, 109091893555309291430933407887392019328056220336914835074665572951469289242157, 90670110792221883996187348700910505681055885477583801408216371226321383082250), (58913256253676878754396772542901058062960739663136672404546218247449955826217, 20476564629519912554045551156054534252670243530526366267884763394482378534287, 43414823558829941459518056527757595345840072122983073739673542488355003785841), (46040503169738671751530280410111756133907287025285732732574646137963898141988, 90038056418055734858233437196561375254873922262665809840608584394489489488219, 52933398566171228428832264505494512086280859410607955234187740679394717003399), (28322564428919492359306157284433228300356912746732283837537184194533070237766, 29160467048185357196899930057099189267580745093622340902659224762309346441214, 26039353134960195170402725279915206394821006686551445832909398074040986084393), (21643642884629372272239257427422434548111071093660016278189319354746988561854, 31263703152705262059536262874656994231536759730561154000449259645368999614764, 105199911349953969667322391118024811020759893123322744450402807102305795159656), (17818375562293210038262569309183431887963616759999164580166459150501562617240, 68709256128099365266791269949117656541683814615625054357862706510892141820878, 68724054513434230732552584911267956250473279585997303572350834208281517688952), (46488526841099552357136658607903610694782584037592204410271971080242497794732, 22280500700029517773383356695696521166361037102529337184897270945540264449488, 106292352202686575557293412717711544291717306594663944198885951077838844230369), (54744569834148748314048978355810647449424503046831552654972076945301737753969, 48598390636071123210548071853272745940731272896777472602381115938455819430802, 110544654813559881208673688219066901740865112556773737149166411878048092007437), (24183091442912524185282519629523932263130931897426402483950594474383857495607, 5086141929975221005656275781445468353799317960140742705329752065204981608145, 100620023044695585644613898936667010326684864572598750259111889731381322340813), (42330455466109742508341894104599280563559287463495821517968429639532359134645, 44924292261952319230418369007369099808082554564871599897592332746013706876704, 70240693395219791641744304573139966488195299647643970164049020659518103179565), (30873674199588312263280989051400695503893758434809750722095730459397008129773, 85687002887482648966286365632763020770625783090855626646288044318704061992398, 38726798613999661261482133360696273360000894413997363296350489598487671807066), (21061375475266480827111086341362443323761389847974735186232979950366078780948, 39345717478281582081752146099293508209186164995099295942813427978917315121612, 4303145176331772274895356697847071390007962769186330891973397374076733831296), (71836515914263137511603033075549707493733097404841325965271406670598051657327, 104949187941865258401710485744737529239458053528810734579776526613256694871588, 46223863810961260605992460270292523432227620490423799813336984029067836931192), (6472181066670151865554687923655274239762670007453239076966086444665009736030, 103657301219312567282166288851937146835288762663288436493406315716582028486335, 23179060229166391936525616790300430138190433638538633937789307644830182202927), (3943075870713949956934984379358132766737763685211205508940763607803387515516, 107144890290963493355297407104644158131965088413544131077537151546644680403374, 110153338056816978556099947913991403004622678694996339328972823398253788963842), (38007566370567363886822508728851512337177336192994339535634073334921123145994, 1718451956071296497063951710564547470677098410718606622164542924310855741230, 21020493579482316538469623244523156826281830248580934928123544005081719293439), (71754547479175731957497895770747906319812332631655894216392250210975293654232, 6436425397057539899435653899833442604312362194787080233245347001285245501781, 6419993035939720501315696960534652280763998311652227591015061863949621803973), (76558620918351656697448366721801622034549874825557870604565139745117540417504, 22271382621497156322785007861677625630147677406263147631868575192142852890723, 69861632402326050501115368835886284065019324782781202826916046056889007431368)]
a=0
b=7
p=115792089237316195423570985008687907853269984665640564039457584007908834671663
ecc=EllipticCurve(GF(p),[a,b])
c1=cipher[0][0]
c2=cipher[1][0]
c3=cipher[2][0]
x1=(c1*pow(65,-1,p))%p #A
x2=(c2*pow(73,-1,p))%p #I
x3=(c3*pow(83,-1,p))%p #S
E1=ecc.lift_x(x1,all=True)
E2=ecc.lift_x(x2,all=True)
E3=ecc.lift_x(x3,all=True)
for i in range(2):
for j in range(2):
for k in range(2):
if(E3[k]-E2[j]==E2[j]-E1[i]):
start=E1[i]
step=E3[k]-E2[j]
#print(start,step)
for i in range(62):
mask=(start+i*step).xy()[0]
plain=(cipher[i][0]*pow(mask,-1,p))%p
print(chr(plain),end="")
# AIS3{it_looks_scary_at_first_but_it_is_actually_pretty_simple}
```
:::
## not_wiener
hint:Coppersmith's method
:::spoiler chal.py
``` python
from Crypto.Util.number import getPrime, bytes_to_long
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
d = phi - getPrime(540) # make sure it is big enough that wiener's attack doesn't work
e = pow(d, -1, phi)
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
```
:::
:::spoiler output
```
n = 17110326996325390716824520634881915298010913120604535776292459924846199689701765864847546766653719661456468857101014445988905339455501258517714801220388003443198794303222048074470666298734166840301928207619060790341511169607101882316448133663573164475042351084351414130983277429007888860759495248971915155878112343745823314128574436282514101062021591704189565257248275643574019426603704130194337517008959429236905944954389702305395308035461002027405904150509876584214818879510367445579266764184153971485632694835699749021921654516650591305120766674204902956230311207675067914081680096189313804247697173127182217459387
e = 7714429763297739382114870300472854141557455369488055430349742307552338983229394632656734813812324873413624727656408209800342411841076931262810669160874776139381307744233254338461862443087819002298123568718355568364460645675817930354022120677573151589733560510499989915954171543144549864469670117875715615212209961007000437000153987237530412998371278147862158402849577523365531182324623606339884685173079048935925934391793489842798280715232033793981950091535161675543153160743302952676927527345929854971822149218166822548710167718216324488288104380822349553511274599485814918489869023398122368429942093008210465747753
c = 14874684651907977995885605300064227182582266550638850330010884768922263112675827661186892697281145324636377811286587623532221444556293695353408598859254787181218157931468216795591221116264875301913885612844282054082972596061689932091582512720822684970814171966613403427307378649796304284665204723148924584345822832050906327259811276226840340198268300944316177613343522948317448524950792221289269986348881301115840492486798083176470781225434854348202043523524873868190296953330399962348090532312096380051872782910645465747040269475324134435269115019811779011252092597033027560579103793160685876383964793544073558741569
```
:::
</br>
這題我沒有解出來，可以去maple3142的github找官解~
Sign in with Wallet
Connect another wallet