Без темы
<<  (Для учащихся 7 класса) (Проект)  >>
(Очень) кратко о криптографии
(Очень) кратко о криптографии
RuCTF
RuCTF
Биты и ключи
Биты и ключи
Биты и ключи
Биты и ключи
RSA
RSA
RSA
RSA
Функция Эйлера
Функция Эйлера
Расширенный алгоритм Евклида
Расширенный алгоритм Евклида
Алгоритм создания public и private keys RSA
Алгоритм создания public и private keys RSA
Пример: Алгоритм создания public и private keys RSA
Пример: Алгоритм создания public и private keys RSA
RSA encrypt/decrypt
RSA encrypt/decrypt
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
Взлом RSA по известному public key
RSA восстановление исходного сообщения
RSA восстановление исходного сообщения
Crypto300
Crypto300
Base64
Base64
MIME(Multipurpose Internet Mail Extension)
MIME(Multipurpose Internet Mail Extension)
Base64
Base64
Base64
Base64
Base64
Base64
Radix-64
Radix-64
Пример email message
Пример email message
Литература
Литература

Презентация на тему: «(Очень) кратко о криптографии». Автор: . Файл: «(Очень) кратко о криптографии.ppt». Размер zip-архива: 389 КБ.

(Очень) кратко о криптографии

содержание презентации «(Очень) кратко о криптографии.ppt»
СлайдТекст
1 (Очень) кратко о криптографии

(Очень) кратко о криптографии

Арыков Никита, nikita.arykov@gmail.com

План лекции Отчет с RuCTF Quals 2012, пример задачи Биты и ключи RSA Взлом RSA(по известному public key) Base64(Radix-64)

2 RuCTF

RuCTF

Российский CTF — 70 команд предпринимало активные попытки сдать задачи Мы заняли 24 место. Сдали 9 задач: joy100, joy200 ppc200, ppc300 admin100, admin400 stegano200 reverse200 forensics400

3 Биты и ключи

Биты и ключи

1 Byte — 8 bit, может принимать одно из 2^8 = 256 значений. Ключ — секретная информация. Длина ключа - количество бит в ключе Если ключ десятичное число 987654321010=10010011001011000000010110111010102 => длина ключа 34бита Вопрос: 128-битный ключ в два раза устойчивее к взлому, чем 64-битный?

4 Биты и ключи

Биты и ключи

НЕТ! Это распространенная ошибка. Каждый дополнительный бит удваивает количество возможных ключей и затраты на полный перебор. Ключ длиной 128 бит является в 2^64 = 18446744073709551616 раз более сложным для подбора, по сравнению с ключом длиной 64 бита. Что такое brute force? Если длина ключа составляет 55 битов, это означает, что необходимо провести 2^55 итераций, что составит 36028797018963968.

5 RSA

RSA

RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Факторизацией натурального числа называется его разложение в произведение простых множителей Криптографическая система с открытым ключом (Асимметричное шифрование) — система шифрования, при которой public key передаётся по открытому каналу. Для расшифровки сообщения используется private key.

6 RSA

RSA

Криптографические системы с открытым ключом используют complexity function, которые обладают следующим свойством: 1) Если известно x, то f(x) вычислить относительно просто 2) Если известно y = f(x), то для вычисления x нет простого (эффективного) пути. Задача факторизации имеет ~ экспоненциальную сложность от размера факторизуемого числа (Класс EXPTIME).

7 Функция Эйлера

Функция Эйлера

Функция Эйлера phi(n), где n — натуральное число, равна количеству натуральных чисел, меньших и взаимно простых с ним. Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. 1) phi(p) = p — 1, если p — простое(то есть все натуральные числа кроме него самого) 2) phi(pq) = phi(p)*phi(q) = (p-1)*(q-1) если p и q взаимно простые

8 Расширенный алгоритм Евклида

Расширенный алгоритм Евклида

Расширенный алгоритма Евклида находит НОД(p,q) = GCD(p, q) = d и такие числа u, v, что p * u + q * v = d. Числа u, v - целые Если числа p и q взаимно простые, то p*u + q*v = 1

9 Алгоритм создания public и private keys RSA

Алгоритм создания public и private keys RSA

1) Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое). 2) Вычислить их произведение n=pq, которое называется modulus(модулем). 3) Вычислить функцию Эйлера от числа n: phi(n) = (p-1)(q-1) 4) Выбирается целое число e(public key exponent) 1 < e < phi(n), взаимно простое со значением функции phi(n). 5) Вычислить число d(private key exponent), такое что e*d = 1 mod phi(n) (взаимно простое по модулю phi(n)). Вычисляется с помощью расширенного алгоритма Евклида 6) Пара {e,n} — RSA public key 7) Пара {d,n} — RSA private key

10 Пример: Алгоритм создания public и private keys RSA

Пример: Алгоритм создания public и private keys RSA

11 RSA encrypt/decrypt

RSA encrypt/decrypt

Для шифрования используется RSA public key {e,n}. Для расшифрования RSA private key {d,n}.

12 Взлом RSA по известному public key

Взлом RSA по известному public key

Задача с RuCTF Quals 2012, crypto300 Условие: расшифровать 2 текста, зашифрованных алгоритмом RSA. Известно два public key и два зашифрованных сообщения Фаилы: {Huian, Siao}.mess - зашифрованные сообщения(числа в десятичной системе счисления). {Huian, Siao}.pub — public keys содержащие модуль n и экспоненту e.

13 Взлом RSA по известному public key

Взлом RSA по известному public key

Huian.pub: n = 1260447419317497339051257660177262242852944409947 e1 = 935152927205491 Siao.pub: n = 1260447419317497339051257660177262242852944409947 e2 = 787779020763001 Huian.mess: 258251903611964818858362251850605663088070061332 Siao.mess: 1192873438825220799434746269282689759605811338951

14 Взлом RSA по известному public key

Взлом RSA по известному public key

1) Производим факторизацию модуля n Используем www.sagemath.org (www.wolframalpha.com не затащил) Factor(1260447419317497339051257660177262242852944409947) = 1116666664279054663729127 * 1128758885384360240791661 Теперь мы знаем p = 1116666664279054663729127 q = 1128758885384360240791661 e1 = 935152927205491 e2 = 787779020763001

15 Взлом RSA по известному public key

Взлом RSA по известному public key

2) Вычисляем функцию Эйлера sage: phi = (p-1)(q-1) phi(pq) = 1260447419317497339051255414751712579438039889160 3) Вычисляем приватные экспоненты d1, d2 sage: d1 = e1.inverse_mod(phi) sage: d2 = e2.inverse_mod(phi) d1 = 375428150796011905336656075893590677053753332211 d2 = 731968282106248361616707347515602329405148111201 Собственно говоря всё — взломали =) Осталось расшифровать

16 RSA восстановление исходного сообщения

RSA восстановление исходного сообщения

Sage: R = integermodring(n) sage: c1 = R(258251903611964818858362251850605663088070061332) sage: c2 = R(1192873438825220799434746269282689759605811338951) sage: c2^d2 239018759833031586337271 sage: c1^d1 239018759833031586337271 - исходное сообщение

Исходное сообщение m = c^d mod n, где с зашифрованное, d — приватная экспонента, n - модуль

17 Crypto300

Crypto300

В задаче необходимо было расшифровать сообщение и открыть архив, в архиве был Central Park.

18 Base64

Base64

Изначально для передачи электронной почты в Интернет использовался только текст (RFC822). Затем, с развитием компьютерных девайсов, потребовалась возможность передачи нетекстовой информации: аудио, видео, графических файлов, файлов приложений и т.д. Однако почтовые сервера как понимали только текст, так и остались понимать только его. Поэтому появилась необходимость каким-то образом преобразовать двоичный файл в текстовый. Тут-то и появился способ кодирования - base64. Этот способ используется в спецификации MIME (RFC2045-2049).

19 MIME(Multipurpose Internet Mail Extension)

MIME(Multipurpose Internet Mail Extension)

MIME - это стандарт описания заголовков e-mail сообщений. Используя этот стандарт, в одном письме можно отправить сразу несколько различных вложений. Например, можно положить в аттачмент письма архивы, фильмы, картинки и т.д. И все это отправить получателю. Почтовая программа-получатель, понимающая MIME, совершенно свободно из файла электронной почты (который на самом деле является "обычным" текстовым файлом) сможет извлечь все фаилы. Некоторые почтовики, например Outlook Express, на радость хакерам без спроса пользователя еще и запустят вложенные в HTML-страницу скрипты.

20 Base64

Base64

Base64 — позиционная система счисления с основанием 64. Base64, используют символы A-Z, a-z и 0-9, что составляет 62 знака, для недостающих двух знаков в разных системах используются различные символы(обычно + и /). Результирующие закодированные по Base64 данные имеют длину, большую оригинальной в соотношении 4:3, и напоминают по виду случайные символы. Здесь 64 — это наибольшая степень двойки 2^6. На один символ приходится 6 бит.

21 Base64

Base64

Один байт - 256 цифр, от 0 до 255. Если вместо восьми бит использовать только шесть, то объем вложенной информации уменьшается до 64 цифр, от 0 до 63. Любую цифру 6-ти битового байта можно представить в виде печатного символа. Берутся три последовательных байта по восемь бит(24 бита), и побитово делятся на четыре 6-ти битных байта (24 бита). Используются только 6 младших бит, два старших бита игнорируются.

В примере три числа 103, 193 и 58 были закодированы в base64 формат. В результате получили 4-х символьный string Z8E6.Двоичная информация перешла в текст по принципу 3 к 4.

22 Base64

Base64

Что делать, если у нас нет трех байтов? Есть только один или два! В этом случае в конец четырех символьного string'а добавляется символ =. Если не хватает (до трех) одного байта, то добавляется один символ "равно": Z8E= Если не хватает двух байт, то добавляются два символа "равно": Z8== Что радует: с символами "равно" надо разбираться только один раз - при чтении конца файла.

23 Radix-64

Radix-64

Radix-64 — разновидность кодирования Base64 двоичных данных в текстовый формат, используемая в PGP. От Base64 отличается тем, что в конец добавляется контрольная сумма в 24 бита.

24 Пример email message

Пример email message

HackQuest4: Расшифровать мое послание =) Полный текст на http://zaic101.ru/daredevil/sql_inj/

Subject: =?UTF-8?B?Vgvzdcbiyxnlnjq=?= Mime-version: 1.0 x-mailer: mpop web-mail 2.19 x-originating-ip: [84.237.53.68] date: sun, 25 mar 2012 18:07:47 +0400 content-type: multipart/mixed; boundary="----d5uprcve-8qvv7ctyheujxp52:1332684467" ------d5uprcve-8qvv7ctyheujxp52:1332684467 content-type: text/plain; charset=utf-8 content-transfer-encoding: base64 sgvsbg8hcgpjigf0dgfjagvkigltywdligfuzcb6axagyxjjagl2zsalkqokls0tls0tls0tls0t ls0ksgfja2vy ------d5uprcve-8qvv7ctyheujxp52:1332684467 content-type: image/png; name="=?Utf-8?B?Yxr0ywnozxjjbwfnzs5wbmc=?=" Content-disposition: attachment content-transfer-encoding: base64 ivborw0kggoaaaansuheugaaawkaaahocaiaaadvag9paaaaaxnsr0iars4c6qaaaarnqu1baacx МНОГА БУКАФ ВЫРЕЗАНО

25 Литература

Литература

Шнайер, Брюс. Прикладная криптография (Applied Cryptography), 2-е издание

«(Очень) кратко о криптографии»
http://900igr.net/prezentacija/bez_uroka/ochen-kratko-o-kriptografii-240580.html
cсылка на страницу

Без темы

23706 презентаций
Урок

Без урока

1 тема
Слайды
900igr.net > Презентации по > Без темы > (Очень) кратко о криптографии