Разбор задач CryptoCTF 2020

ASIS cryp.toc.tf/

Модульная арифметика
Простое число - натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя.
Взятие x по модулю (x % m) – вычисление остатка от деления x на m
a и b сравнимы по модулю m, если их остатки при делении на m равны (a ≡ b % m ). Класс вычетов – множество всех чисел, сравнимых с a по модулю m.
Отношение сравнимости является отношением эквивалентности (симметричным, транзитиным, рефлексивное)
Допустимые операции со сравнениями: a + m * x ≡ b % m; a - b ≡ 0 % m; a + x ≡ b + x % m; a * x ≡ b * x % m; ax ≡ bx % m; a / k ≡ b / k % m если НОД(k, m)=1
Обратное число по модулю – такое i, что a * i ≡ 1 % m. Существует для всех a, взаимнопростых с m
Теорема Эйлера: aφ( n ) ≡ 1 % m, φ(m) - функция Эйлера (количество натуральных чисел, не превышающих n и взаимно простых с ним)

Encoding

Abbot

Abbot

Amsterdam

Amsterdam

Shift registers

Heaven

Heaven

Heaven
1)

Heaven
2)

Heaven
2)

Knapsack

Namura

Namura

Namura

Matrices

Mad hat
m – искомый вектор
K, d – закрытый ключ
K – матрица, d – натуральное число
с = m * K +
+ [d, d … d]

Mad hat
1) Какие передаваемые или генерируемые в самой функции параметры определяют ключевую матрицу?

Mad hat
2) как именно они влияют и что нужно для их нахождения
p можно определить по размерности шифртекста:
p1 = 37
p2 = 75
Для d имеет значение только четность

Mad hat

Algebraic

Gambling
nc 05.cr.yp.toc.tf 33371
p, a, b – не известны
f(x) ≡ x3 + ax + b % p
f(flag) = c
Мы можем получить f(x) для любого x

Gambling
nc 05.cr.yp.toc.tf 33371
p, a, b – не известны
f(x) ≡ x3 + ax + b % p
f(flag) = c
Мы можем получить f(x) для любого x
f(0) ≡ b % p – получаем b
f(1) ≡ 1 + a + b % p – получаем a
c1 = x13 + ax1 + b = f(x1) + k1p
c2 = x23 + ax2 + b = f(x2) + k2p
НОД (c1 – f(x1), c2 – f(x2)) делится на p
Решаем сравнение:
x3 + ax + b – с ≡ 0 % p

Algebraic, pow

One line crypto
p = xm+1 - (x+1)m
q = ym+1 - (y+1)m

One line crypto
p = xm+1 - (x+1)m
q = ym+1 - (y+1)m

Three ravens
p, q, r – простые (секретный ключ, не известны)
s = p + q + r - простое
n = p * q * r * s
s, n / s – открытый ключ, известны
с = me % n
m = ?

Three ravens
Короткое сообщение (< длины любого из множителей n)
Известен один из множителей n
c ≡ me % p*q*r*s
c_ = me = k * (p*q*r*s) + c
me ≡ c % s
d ≡ e-1 % s
cd ≡ med ≡ m % s

Model
nc 04.cr.yp.toc.tf 8001
p, q – простые
P = (q-1) // 2
Q = (p-1) // 2
r ≡ Q-1 % P
e = 2 * r * Q - 1
c ≡ me % p*q

Model
nc 04.cr.yp.toc.tf 8001
p, q – простые
P = (q-1) // 2
Q = (p-1) // 2
r ≡ Q-1 % P
e = 2 * r * Q - 1
c ≡ me % p*q
e = 2 * Q-1 * Q - 1 = 1 % P
1) e ≡ 1 % (q-1)
c ≡ m % q
1) e ≡ 1 + P % (q-1)
c = m1+(q-1)/2 % q
c = m*11/2 % q
c = ± m % q
q = gcd(c ± m, n)

Butterfly effect

Butterfly effect

Butterfly effect
https://blog.cryptohack.org/cryptoctf2020

Decent RSA
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA/Ug8rlEPci1UXMsT+UDo
y8DfxbTHX/3BK2oU+FPWiJf+EiUBM2x4ep04qZ1SO9Pmqj/WH9skMrF1J/LXuY3l
fjvJCh0DXa9VUyX2dAJidja9Ior7GpFwwjYdKh+OETNV+2/CcX4RiPvj+8ApmedW
gn4Fxaeivki+f/UwDa+ws1fTUzmI325v8yvcryHhbgeUWiF85EP6HFAavTsVPlxb
LikVMAB1fuzDbqqJvW2u138w6b2FH3WrezYF6tbAyZej2HX46phwDm9C7MXYJ/sU
oS+E8P7S1jMTCWjfwMCOKU3SFGrkWtXuTaoMZ2nZ+HVfJV8xJOjWez1OxQ5P3F1w
GQIDAQAB
-----END PUBLIC KEY-----

Decent RSA
Official writeups
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA/Ug8rlEPci1UXMsT+UDo
y8DfxbTHX/3BK2oU+FPWiJf+EiUBM2x4ep04qZ1SO9Pmqj/WH9skMrF1J/LXuY3l
fjvJCh0DXa9VUyX2dAJidja9Ior7GpFwwjYdKh+OETNV+2/CcX4RiPvj+8ApmedW
gn4Fxaeivki+f/UwDa+ws1fTUzmI325v8yvcryHhbgeUWiF85EP6HFAavTsVPlxb
LikVMAB1fuzDbqqJvW2u138w6b2FH3WrezYF6tbAyZej2HX46phwDm9C7MXYJ/sU
oS+E8P7S1jMTCWjfwMCOKU3SFGrkWtXuTaoMZ2nZ+HVfJV8xJOjWez1OxQ5P3F1w
GQIDAQAB
-----END PUBLIC KEY-----