Одинаковые шифртексты при грубом взломе
Люди у меня такой вопрос. Допустим, есть некий алгоритм, симметричный блочный шифр. Размер ключа – 128 бит, блока – 64 бит. Я правильно понимаю, что:
1. Всего ключей – 2^128.
2. Всего возможный шифртекстов – 2^64.
3. Есть 64-разрядный вектор данных – открытый текст (А), есть шифртекст (Б) от ключа К.
Если перебирать по всему ключевому пространству, зашифровывая блок А, то каждый из 2^64 ключей (2^128/2^64) будет создавать один и тот же шифртекст Б? Т.е. одного блока данных для грубого взлома недостаточно?
Ссылки
[link1] https://www.pgpru.com/proekt/poljzovateli?profile=unknown
блин. вот новая формулировка
Если перебирать по всему ключевому пространству, зашифровывая блок А, то каждый 2^64 ключ (2^128/2^64) будет создавать один и тот же шифртекст Б? Т.е. одного блока данных для грубого взлома недостаточно?
Вы не боитесь, что unknown[link1] вам кол поставит за то что вы не посещали занятия? Учитесь пока не позно – иначе шифровальщицы с вас не выйдет.
1. -цы? Абитура-это собирательное название абитуриентов в вузы. вообщето я – ОН. ))
2. Какие еще занятия? Причем тут шифрование – я спрашиваю о грубом взломе.
3. Вы можете просто ответить на вопрос?
Можно. Недостаточно.
А посмеялся народ потому что переводил "Brute force attack" как "взлом грубой силой" или "полным перебором", а с Вашим вариантом не сталкивался...
Да, это именно тривиальный случай брутфорса.
Блочный шифр – это функция псевдослучайной перестановки (Pseudo Random Permutation) вида E: {0,1}k x {0,1}n -> {0,1}n,
где k – размер ключа, n – размер блока. Каждому значению блока исходного текста M размером n соответствует единственно возможный шифртекст C такого же размера. Если все возможный значения M (в нашем случае 264) можно было бы записать в таблицу, то все соответствующие значения C будут представлять псевдослучайную перестановку из всего множества значений M, задаваемую ключём. Каждый новый из 2128 бит ключей будет задавать новую PRP-таблицу.
Пусть нам известен блок открытого текста M и соответствующее ему значение C.
Будем пытаться (Try) подобрать ключ методом перебора.
Если ET(M)=C, то (в большинстве случаев) T = K. Подобраный ключ равен искомому.
Какова вероятностьв этом случае, что подбираемый ключ T случайно выдал нужный шифртекст и не совпадает с K ?
Pr1 [ T <не равно> K ] = 1/(264)
Значит, достаточно взять этот ключ и попробовать зашифровать им другой известный блок открытого текста:
Если ET (M1) = C1 и ET (M2) = C2, то с большой долей вероятности можно утверждать что ключ верный.
Какова вероятность ошибки на двух блоках?
Pr2 [ { ET (M1) = C1 и ET (M2) = C2 } при T <не равно> K ] = 1/(264)
Произведение Pr1 x Pr2 = 1/(2128).
Т.е. проверки ключа на двух известных блоках открытого текста достаточно в абсолютном большинстве случаев, а затраты на дополнительную проверку ключей-кандидатов ничтожны по сравнению с общим пространством перебора ключей. И как правило действительно необходимо знать именно два блока, а не один.
"-перебор по всему ключевому пространству"-термин используется(-лся) в ссср/снг. да, народ использует переведенные книги, т.к. наша лит-ра закрыта.
2unknow
при данном случае? Т.е. вероятность ошибки на двух блоках при k-key, m-ciphertext: 2^(-[k-m])?
вообще все это странно.
смотрите:
возьмем простой блочный шифр
блок – 8 бит
ключ 16 бит
правило зашифрования: T=(C+K) mod 256
кидаю прогу:
#include <stdio.h>
void main()
{
int t; //text
int c; //tipa ciphertext
int A[256]={0}; //eto tipa sschetcih shifrtekstov
int i; //prosta schetchik
for(k=0;k<65536;k++)
{
A[c]++;
каждый ключ создает одинаковых 256 шифртекстов
т.е. 2^(k-m), где к-ключ, m-блок (размер в битах)
мб при блоке в 64 бит и 256 битовом ключе (ГОСТ) создается 2^192 одинаковых блоков, и, чтобы брутфорсить (ну и глагол!) ГОСТ надо 4 блока.
<Pr1 [ T <не равно> K ] = 1/(2^64)?
Pr1 [ T <=> K ] = 1/(2^64)!
Pr1 [ T <не равно> K ] = (1-1/(2^64))!
разве не так?
Если нет, то для тех кто на бронепоезде пожалуйста поподробнее.
Так речь о том, что при переборе ключей вероятность Pr двух ошибочных совпадений подряд (успешной расшифровке ошибочным кандидатом двух известных блоков) при таком большом пустом пространстве неподходящих блоков ничтожно мала и нет смысла доводить её до 1 (в отличие от вышеприведённого примера с малым размером блоков и неслучайным распределением, распределение в реальном шифре будет псевдослучайным, никакой определяемой закономерности). Реально достаточно только двух блоков. По ним можно взять найденный ключ-кандидат и уже вручную попытаться расшифровать весь шифртекст и смотреть что получиться.
Но если совсем не хотите получать ложных тревог, ну тогда да, надо знать 4 блока текста, но на практике всегда достаточно двух (если брутфорс можно считать практикой ;-).
// – Товарищ Сталин, мы можем спрогнозировать исход этого сражения с точностью до 40%!
– А вы спрогнозируйте и напишите в докладе наоборот, чтобы повысить точность до 60%. //
Кстати да, в случае с одним блоком всё наоборот, как в анекдоте, мы знаем одну пару M->C из 264 возможных. А ключей 2128, значит каждая пара указывает на 264 ключей, Pr1 [ T<=>K ] = 1/(264)
Абитура – Есть еще парочка советов.
Стучи в аську, помогу разобраться. 493266451