РегистрацияОдинаковые шифртексты при грубом взломе
Люди у меня такой вопрос. Допустим, есть некий алгоритм, симметричный блочный шифр. Размер ключа – 128 бит, блока – 64 бит. Я правильно понимаю, что:
1. Всего ключей – 2^128.
2. Всего возможный шифртекстов – 2^64.
3. Есть 64-разрядный вектор данных – открытый текст (А), есть шифртекст (Б) от ключа К.
Если перебирать по всему ключевому пространству, зашифровывая блок А, то каждый из 2^64 ключей (2^128/2^64) будет создавать один и тот же шифртекст Б? Т.е. одного блока данных для грубого взлома недостаточно?
Если перебирать по всему ключевому пространству, зашифровывая блок А, то каждый 2^64 ключ (2^128/2^64) будет создавать один и тот же шифртекст Б? Т.е. одного блока данных для грубого взлома недостаточно?
2. Какие еще занятия? Причем тут шифрование – я спрашиваю о грубом взломе.
3. Вы можете просто ответить на вопрос?
комментариев: 83 документов: 4 редакций: 4
А посмеялся народ потому что переводил "Brute force attack" как "взлом грубой силой" или "полным перебором", а с Вашим вариантом не сталкивался...
комментариев: 9796 документов: 488 редакций: 5664
Блочный шифр – это функция псевдослучайной перестановки (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-блок (размер в битах)
Pr1 [ T <=> K ] = 1/(2^64)!
Pr1 [ T <не равно> K ] = (1-1/(2^64))!
разве не так?
Если нет, то для тех кто на бронепоезде пожалуйста поподробнее.
комментариев: 9796 документов: 488 редакций: 5664
Но если совсем не хотите получать ложных тревог, ну тогда да, надо знать 4 блока текста, но на практике всегда достаточно двух (если брутфорс можно считать практикой ;-).
комментариев: 9796 документов: 488 редакций: 5664
// – Товарищ Сталин, мы можем спрогнозировать исход этого сражения с точностью до 40%!
– А вы спрогнозируйте и напишите в докладе наоборот, чтобы повысить точность до 60%. //
Кстати да, в случае с одним блоком всё наоборот, как в анекдоте, мы знаем одну пару M->C из 264 возможных. А ключей 2128, значит каждая пара указывает на 264 ключей, Pr1 [ T<=>K ] = 1/(264)
Стучи в аську, помогу разобраться. 493266451