---
# System prepended metadata

title: Крипта

---

## №8 RSA

0. Шифрование с закрытым ключом.

2. Что такое группа
    Что мы любим о наших числах? А конкретно о наших целых числах с операцией умножения. (написать на доске $\mathbb{Z}^*$ -- мы будем называть так целые числа и операцию умножения на них)
    1. Замкнутость $\forall a, b: a*b \in \mathbb{Z}$
    2. $\forall a, b, c: (a*b)*c = a*(b*c)$
    3. $\exists e: , a*e = a$
    4. $\forall a\exists b=a^{-1}, a*b = a*a^{-1} = e$
    
    https://ru.wikipedia.org/wiki/%D0%93%D1%80%D1%83%D0%BF%D0%BF%D0%B0_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
    
2. Модульная арифметика
    также есть чудесное свойство у функции остатка от деления, которую вы скоро очень полюбите

3. Мультипликативная группа остатков
    https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BF%D0%BB%D0%B8%D0%BA%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_%D0%BA%D0%BE%D0%BB%D1%8C%D1%86%D0%B0_%D0%B2%D1%8B%D1%87%D0%B5%D1%82%D0%BE%D0%B2
   На доске 1->9 и вниз их циклы
   Все числа, которые не взаимно просты с 9, заканчиваются на 0 и не циклятся. Это неудобно, потому что дальнейшее умножение на что угодно делает всё нулем. Давайте их зачеркнем и забудем
   Назовем нашу группу $G$
   Тот факт, что для любого числа верно то, что $a^{|G|} = 1 \mod n$ -- теорема Эйлера, а $|G|$ такой группы по числу $n$ называется $\phi(n)$ - функция Эйлера


4. Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:
    - если известно $x$, то $f(x)$ вычислить относительно просто;
    - если известно $y = f(x)$, то для вычисления $x$ нет простого (эффективного) пути.

    В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа

4. Чудом вышло, что на этих сущностях мы можем делать криптосистему.
    Давайте представим что у нас есть группа остатков по модулю N и мы будем опираться на тот факт, что будет сложно получить $\varphi(n)$. $\varphi(n)$ знакомого числа узнать несложно -- надо перемножить все простые множители n - 1 - $\prod(p-1)$, однако проблема -- факторизовать на множители простое $n$ можно чуть лучше чем за $\sqrt n$ проверок. И для числа например примерно 512 бит корень из него это очень много
5. рса.
    
    choose $p, q - prime$ 512+ bit, $n = pq$
    $e = 65537$, and $d$ such as $ed = 1 \mod \varphi(n)$ (`d = pow(e, -1, \phi(n))`) обратное в мультипликативном кольце по модулю фи

    $c = m^e \mod n$

    $c^d = m^{e^d} = m^{ed} = m^{\varphi(n) + 1} = m^{\varphi(n)} * m = m \mod n$


Задачи:
1. даны p, q, e; найти (d, n) и расшифровать сообщение
2. (n, e): факторизовать n
3. N состоит из очень близких простых чисел <=> $|p-q|<10^6$ ==> https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
4. Blinding
5. та задача на другую систему (в закрытую)
6. Олдовая (в закрытую)

---

- пришло 6

## №7 Генерация псевдослучайных чисел

Тизер

Сегодня мы научимся предсказывать будущее: 
```python
from random import randint

for _ in range(1000):
    key = randint(0, 2**32)
    if input("input key: ") == key:
        print(flag)
    else:
        print(f"No. key was {key}")
```
Сможете достать флаг?
в конце занятия сможете

---

Как вы, наверное, поняли, сегодня мы поговорим о случайных числах и случайности. Давайте для начала подумаем, что такое генератор случайных чисел.

Энтропия = мера случайности. Я буду использовать это слово как замену слова "случайность" иногда

<!-- У генераторов случайных чисел есть два свойства -->
Что мы хотим, от идеального генератора случайных чисел?

1. Равномерное распределение
2. Независимость / Непредсказуемость (криптографичность): имея сколь угодно длинную последовательность сгенерированных чисел, мы не можем угадать ни одно из следующих чисел

> Может ли генератор случайных чисел иметь непредсказуемость но не иметь равномерное распределение? Может, например ваш рост

По-настоящему случайные числа возможно получить только из реальности: например из данных с термометров на платах, радиационного фона. На наших компьютерах, ядро linux (до 5.6, 2020) снимает телеметрию с мышек, клавиатур, времен ответа дисков ([1] 10.9.1) и генерирует некоторую случайную криптоустойчивую последовательность из этого в /dev/random. Однако эта последовательность генерируется очень медленно (в ней мало бит/секунду), так что мы не сможем использовать для всех наших случайных чисел [1]. Этот феномен кстати называется Софтверный источник энтропии, против источников энтропии из реальной жизни.

> In 2020, the Linux kernel version 5.6 /dev/random only blocks when the CPRNG hasn't initialized. Once initialized, /dev/random and /dev/urandom behave the same.[17] 

Из настоящих источников энтропии мы каши не сварим, они генерируют недостаточно много бит. Как мы можем с этим смириться? Мы можем генерировать биты с помощью псевдослучайных алгоритмов! Алгоритмы генерации псевдослучайных чисел часто инициализируются алгоритмами более случайных случайных чисел.

Не все генераторы псевдослучайных чисел реализуют оба наших требования. Часто дешевые генераторы можно предсказать.

генераторы псевдослучайных чисел бывают криптографическими (PRNG) и не криптографическими (CPRNG)

Давайте рассмотрим несколько вариантов этих генераторов

#### рассказать про LCG

Статья на русском даже с меньшим числом буллщита рассказывает о LCG.
https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B3%D1%80%D1%83%D1%8D%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4

#### GFSR 
https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D0%B8%D1%81%D1%82%D1%80_%D1%81%D0%B4%D0%B2%D0%B8%D0%B3%D0%B0_%D1%81_%D0%BE%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D1%8C%D1%8E

У нас есть какое-то состояние из N чисел. Следующее число можно вычислить по предыдущим. Это похоже на какую-то микросхему какой-то регистр.



#### рассказать про Mersenne Twister
Очень быстрый генератор, который используется всеми языками по умолчанию. Например в питоне, пример который я показывал в начале урока, используется mersenne twister, или MT19937. 

#### рассказать про использование шифрования: например AES по нистовому протоколу из [1]

- ядро юзает https://en.wikipedia.org/wiki/Salsa20#ChaCha_variant для /dev/urandom. По сути тоже шифрует предыдущее значение

[1] https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture10.pdf 10.5

[2] https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Uses_in_cryptography

[3] https://docs.python.org/3/library/random.html

[] https://en.wikipedia.org/wiki/Diehard_tests



https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Xorshift_LFSRs
https://en.wikipedia.org/wiki/Xorshift
https://en.wikipedia.org/wiki/Diehard_tests
https://en.wikipedia.org/wiki/Linear_congruential_generator
https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D0%B8%D1%81%D1%82%D1%80_%D1%81%D0%B4%D0%B2%D0%B8%D0%B3%D0%B0_%D1%81_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B9_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D1%8C%D1%8E
https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D0%B8%D1%81%D1%82%D1%80_%D1%81%D0%B4%D0%B2%D0%B8%D0%B3%D0%B0_%D1%81_%D0%BE%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D1%8C%D1%8E
https://en.wikipedia.org/wiki/Recurrence_relation

https://www.schutzwerk.com/en/blog/attacking-a-rng/
https://cryptopals.com/sets/3/challenges/23

Задачки:
1. Про LCG с известными параметрами +
2. LCG, time() initialised +
3. random.seed(time()) +
4. Mersenne twister with bad tampering
5. random.randint() with hint: use libraries
6. Final boss: Mersenne twister


---
### №5
Костыль: продолжение AES (у меня ещё и онлайн пара будет)

- разобрать why we need AES
- Дать AES-ECB one at a time
- bitflipping если успеваем
- пришло 5

---

---
- матвею очень понравилось когда он понял
- Пришло 10
- не успели даже why we need aes, хотя я дал сурсы всего кроме 5-тистрочного repeated-key xor *shrug*, но чуваки энивей много всего поняли
## №3-4 AES 
1. По сути, сегодня мы продолжим наш предыдущий урок, но, чтобы все начинали с одного момента, я выдам вам код, уже решающий однобайтовый XOR и достаточно неплохо. Мне кажется, что я написал его достаточно аккуратно и удобно, так что вы можете смотреть на него как на пример.
2. (задача 2) Repeating Key XOR (зная длинну ключа). Для челов которые уже сделали его сказать решить его с неизвестным ключом.
    (разминка 1) реализовать pkcs7 (pad + unpad)
4. Блочные шифры: AES
    AES - американский стандарт шифрования данных (fyi есть ещё некие русские ГОСТы, но я о них ничего не знаю). Сам по себе он определяет магическую функцию, которая шифрует блоки по 128, 198 или 256 бит, сегодня мы будем считать её идеальной и криптостойкой. Также, чтобы шифровать этой функцией большие тексты, нужно понять, как разумнее ей пользоваться, для этого есть разные режимы блочной криптографии.
    https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
    (задача 3) Why we need AES?
    (задача 4) AES-ECB one at a time (why we need CBC)
2. Также, если длина сообщения не делится на блоки, это сообщение нужно как-то расширить. По-английски это называется padding и на нём тоже основывается пара атак
    - (bitflipping) https://cryptopals.com/sets/2/challenges/16 
3. Случилось чудо
    - padding oracle
    

AES https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture8.pdf

---
- дошли только до repeated-key XOR
- пришло 6
## №2 Repeating-key XOR

Сегодня поговорим о симметричной крипте

TODO сделать нормальное интро с определениями, спиздить здесь https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture2.pdf

Пользоваться тулзами нельзя, сегодня и дальше мы почти всё делаем руками. На сложных задачках конечно можно пользоваться, но цель тут -- разобраться, как оно работает.
НЕ ПРОГРАММИРУЙТЕ КРИПТУ. МЫ ДЕЛАЕМ ЭТО ЧТОБЫ РАЗОБРАТЬСЯ, КАК ОНА РАБОТАЕТ. Реализовывать свою крипту это полнейший путь к провалу
1. XOR разминочка
    Задачка. https://cryptopals.com/sets/1/challenges/2
    Дать небольшую штуку с кодом, можно прям ноутбук, я думаю, в котором будет работа с байтами, и чувакам надо посчитать чему равен ксор двух строчек
2. one-byte XOR
    Задачка. https://cryptopals.com/sets/1/challenges/3
    *: https://cryptopals.com/sets/1/challenges/4
3. Repeating key XOR
    Чем отличается наша задача, если ключ будет некоторой длинны? Можем ли мы угадывать длинну?
    https://cryptopals.com/sets/1/challenges/6
    Про хемминговое расстояние

> Почему хемминговое расстояние?
https://crypto.stackexchange.com/questions/8115/repeating-key-xor-and-hamming-distance

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
https://www.kavaliro.com/wp-content/uploads/2014/03/AES.pdf
мб https://thmsdnnr.com/blog/lets-code-aes-aes-in-ecb-mode/

Задачи
1. Поксорить две строчки своим кодом
3. Реализовать расстояние хемминга
    - Почему расстояние хемминга у двух настоящих блоков будет меньше, чем расстояние хемминга у двух не настоящих?
4. Сломать one byte XOR через перебор и статистику
5. Сломать repeating-key XOR зная длинну ключа
6. не зная длинну ключа
7. AES-ECB one at a time.
    сервис `AES-128-ECB(your-string || unknown-string, random-key)`
    достать unknown string
6. block-XOR CBC. через repeating key XOR "Why we need AES?"
9. CBC bitflipping?

---
- пришло 10
## №1 Хеширование

### теория
https://en.wikipedia.org/wiki/Cryptographic_hash_function
https://en.wikipedia.org/wiki/Hash_function
У нас будет ориентированное на практику сегодня занятие, и мы поговорим (а точнее подумаем) про хранение паролей. Все сайты иногда взламывают, но не всегда когда сливают всю базу данных сайта, вы можете узнать логины и пароли. 

Давайте придумаем, как этого можно достичь.

Но сначала давайте вспомним о том, как строчки хранятся в компьютерах. Немного обобщая, у каждого символа в алфавите есть какое-то численное представление строгой длинны

Ситуация 1: стартовая. Есть таблица users, в которой лежит логин юзера и пароль. Когда такую таблицу сливают, пароли всех пользователей становятся общественным достоянием

Как это решить?
Давайте введём некую математическую функцию, которая переводит строки любой длины (пароли) в числа. Причем эта функция должна быть такой, что по данному числу, мы не можем узнать пароль. Такие функции называются криптографическими хеш-функциями. Где
1. Криптографичесими – по данному результату функции практически невозможно определить входные данные
2. хеш-функциями – выходные данные это числа фиксированной длины

К задаче нахождения такой функции мы ещё вернемся.

Ситуация 2: храним юзернейм, хеш от пароля. Когда хакеры получают доступ к таблице, им нужно перебирать все варианты паролей чтобы узнать пары (юзернеймов, паролей). Уже неплохо.

Однако, новая проблема: хакеры очень неплохо перебирают пароли. В мире есть популярные хеши как MD5, SHA256 и для них и для частых паролей, все хеши уже подобраны, так что часть пользователей, которые не умеют придумывать хорошие пароли остается в опасности.
Бонус-очки: вы можете найти в интернете сайты, которые расшифруют вам хеши на рас-два

Как это решить?
В нашу таблицу добавляется дополнительное поле, в которое при регистрации присваивается случайное число -- назовём его соль. И сохраняем хеш мы от соединенных двух строк -- пароля и соли. Так, хакеры не смогут перебрать все наши пароли одновременно и пользоваться готовыми таблицами. Только перебирая пароли по одному они что-то смогут узнать

Ситуация 3: юзернейм, соль, хеш. Хакеры перебирают пароли по одному и всё равно продают наши данные на своих сайтах.

Как мы можем сделать их жизнь хуже? Сделаем так, чтобы наш хеш считался долго. Например, можно хранить не 1 итерацию хеша, а 1000-ную. Так вроде бы работает авторизация в линуксе.

### Бонус: Придумать хеш



### Задачки
- md5_lox hash length extension attack https://en.wikipedia.org/wiki/Length_extension_attack 
    - Хорошая статья https://www.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks
- почитать про хеши и сочинить свой, какой-нибудь плохой и сделать из него свою
- не крипто хеш
- дана табличка с юзерами надо зайти за кого-то из них
- rolling hash easy (1)
- rolling hash with collisions (2)

1. md_kochan_extension attack
2. md5 extension attack
3. hashcat скрипткиддинг (опционально)
4. атака на кривую хеш мапу (показывает импакт от коллизий)
5. табличка с сша256 из таблиц -- никита
6. роллинг с коллизией
7. роллинг аналитически
8. sha256(sha256("ctf"))
9. md5("hello")

https://yandex.ru/jobs/pages/appseceng-interview

md5 collisions https://www.mscs.dal.ca/~selinger/md5collision/
