Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм Френдберга. Дешифрование

Автор: Rijndael 22.3.2008, 16:29

Код 6.2.4. Комбинированные meтоды     Шифрование   комбинированными   методами   основывается    на результатах, полученных К.Шенноном.  Наиболее  часто  применяются такие комбинации, как подстановка и гамма, перестановка и гамма , подстановка и перестановка, гамма и гамма.     В   качестве   примера    рассмотрим    шифр,    предложенный Д.Френдбергом   [6],    который    комбинирует    многоалфавитную подстановку с генератором псевдослучайных чисел,  суть  алгоритма поясняется схемой, подставленной на рис.6.5.     Особенность данного алгоритма состоит в том, что при  большом объеме шифртекста частотные  характеристики  символов  шифртекста близки к  равномерному  распределению  независимо  от  содержания открытого текста.    1)Установление начального состояния генератора псевдослучайных чисел    2)Установление начального списка подстановки    3)Все символы открытого текста зашифрованы?    4) если да - конец работы, если нет -продолжить    5)осуществление замены    6)генерация случайного числа    7)перестановка местами знаков в списке замены    8) переход на шаг 4      Рисунок 6.5 Схема алгоритма Д. Френдберга  Пример 6.16. Открытый текст: "АБРАКАДАБРА".  Используем одноалфавитную замену согласно таблице 6.8.    Таблица 6.8       А Б Д К Р       X V N R S     Последовательность    чисел,     вырабатываемая     датчиком: 31412543125.     1.  у1=Х.  После  перестановки  символов  исходного  алфавита получаем таблицу 6.9 (h1=3).  Таблица 6.9     Д Б А К Р     X V N R S     2. у2=V. Таблица 6.9 после перестановки (h2=1) принимает вид, представленный в таблице 6.10.         Таблица 6.10           Б Д А К Р           X V N R S     Осуществляя  дальнейшие  преобразования  в   соответствии   с алгоритмом Френдберга, получаем шифртекст: "XVSNSXXSSSN". Использую этот метод. Не могу придумать алгоритм дешифрования шифротекста зная только шифротекст и ключ. Например: слово: АБРА алфавит: X   P   V А   Б   Р сгенерирован ключ 312. на выходе получаем: PPPV. Как теперь расшифровать сие чудо?

Автор: Rijndael 23.3.2008, 15:31

Возможно, кто-нибудь подкинет материалы по данному алгоритму?

Автор: v2v 24.3.2008, 21:26

Цитата(Rijndael @  22.3.2008,  16:29 ) на выходе получаем: PPPV.  помоему это не правильно.

Автор: Rijndael 25.3.2008, 02:52

Ошибся, алфавит: X P V Р А Б но вопрос - как это расшифровать - не решен.

Автор: Alexandr87 25.3.2008, 09:21

Цитата Установление начального состояния генератора псевдослучайных чисел подразумевается, что при установке одного и того же начального состояния ГПСЧ будет выдавать одинаковую последовательность. Дальше думаю, все понятно.

Автор: v2v 25.3.2008, 09:25

Если я правильно понял метод , то должно быть так:  Открытый текст : АБР Ключ : 312 Алфавит XPV шифрование:  начальное состояние АБР XPV меняем 1й элемент и 3й: РАБ XPV меняем 2й элемент и 1й: АРБ XPV меняем 3й элемент и 2й: АБР XPV вот эту последнюю подстановку наверное надо отправлять получателю, а также ключ 312 , по секретному каналу, он выполняет расшифровку в обратную сторону и получает открытый текст. Я правильно понял алгоритм?

Автор: Rijndael 25.3.2008, 09:36

Alexandr87, нет, не понял. Естественно, мы в итоге имеем шифротекст и ключ, который и является этой самой последовательностью чисел-перестановок. Но Загвоздка в том - не пойму, каким- образом их использовать, т.к. мы имеем только зашифрованное сообщение и первоначальный (!), не модифицированный алфавит. Возможно я не правильно понял сам алгоритм (хотя, исходя из схемы, все должно быть правильно), если бы была какая-нибудь инф. о нем....гугл находит одну страницу, и только. v2v, правильно, только отправить нам необходимо не ключ и алфавит а ключ и зашифрованное сообщение (т.е. получившееся АБР, используемое для взятия соответствующих символов из второго, английского алфавита собственно с целью закодировать ими открытый текст, мы никуда не пересылаем). Естественно, что если бы конечный пользователь имел в распоряжении сообщение, этот перестановленный алфавит и ключ, то получение исходного сообщения не вызывала бы вопросов. Но и смысл самого алгоритма шифрования пропадает, т.к. в этом случае его можно расписать за пару минут прямо на бумаге.

Автор: v2v 25.3.2008, 12:25

Цитата(Rijndael @  25.3.2008,  09:36 ) шифрования пропадает, т.к. в этом случае его можно расписать за пару минут прямо на бумаге. нет. не возможно. суть в том, что взломщик не знает ключа, и не знает какие перестановки выполнять. давай на изначальном примере. для того что - бы расшифровать текст, получателю как минимум надо: шт: XVSNSXXSSSN а также вероятней всего начальную подстановку       А Б Д К Р       X V N R S взломщик имея эту подстановку и шифр текст получит белеберду,  а получатель , зная 31412543125 нормально расшифрует. скорее всего как сказал Alexandr87 эта подстановка может быть сгенерирована как отправителем , так и получателем и будет одинаковая (это открытая часть).

Автор: Rijndael 25.3.2008, 13:02

Пользователь по идее не сможет сгенерировать подстановку, т.к. подстановка зависит не только от цифр ключа, но и от букв оригинального сообщения. Как-же мы сгенерируем подстановку, если у нас этих букв нет, а есть только ключ и бесполезный на данном этапе шифротекст? Цитата подразумевается, что при установке одного и того же начального состояния ГПСЧ будет выдавать одинаковую последовательность. Будет, но при условии оригинального сообщения. А его у нас как раз нет и быть не может. Имея лишь начальную подстановку и ключ, конечную подстановку мы собрать не можем, т.к. не знаем, какие буквы надо менять местами. Цитата а получатель , зная 31412543125 нормально расшифрует.

Автор: Alexandr87 25.3.2008, 16:07

v2v, попутаны понятия. Ключом в данном случае является начальная таблица перестановки. Значение инициализатор ГПСЧ - может и не является ключом (а можно и ввести как дополнительный элемент ключа). ГПСЧ используется исключительно для усложнения частотного криптоанализа. Теперь по тому, с чем у вас возникли трудности Цитата(Rijndael @  25.3.2008,  16:02 ) Имея лишь начальную подстановку и ключ, конечную подстановку мы собрать не можем итак, по примеру приведенному в описании алгоритма. (в сокращении) Шифрование: Открытый текст: абра Сгенерированная последовательность: 3141 таблица подстановок: 1 шаг АБДКР XVNRS X 2 шаг АБАКР XVNRS V 3 шаг БДАКР XVNRS S 4 шаг БДАРК XVNRS N Расшифровывание: Закрытый текст: XVSN Сгенерированная последовательность: 3141 таблица подстановок: 1 шаг АБДКР XVNRS Первый символ в шифртексте X, значит первый символ в откртом тексте был А Меняем A с 3 2 шаг ДБАКР XVNRS V->Б Меняем Б c 1 символом 3 шаг БДАКР XVNRS S->Р (меняем с 1) 4 шаг РДАКБ XVNRS N->А и т.д. Мы восстанавливаем таблицы замен на каждом шаге.

Автор: Rijndael 25.3.2008, 19:18

Хм, до этого сидел, считал, с косяками получалось, сейчас все сошлось и ясно. Большое спасибо

Автор: Pubman 4.4.2008, 16:21

аааааа *мозг ушел в ребууут* Помогите пожалуйста разобраться с этим алгоритмом. Вот к примеру у нас есть АБРАКАДАБРА Буквы, которые используются - АБДКР. Каким образом получается XVNRS ??? Или мы генерируем случайно эти буквы? Сгенерированная последовательность 3141....... ОТкуда она берется? Генерируется рандом-ом или по какому-то закону в зависимости от букв7???? Цитата Шифрование: Открытый текст: абра Сгенерированная последовательность: 3141 таблица подстановок: 1 шаг АБДКР XVNRS X 2 шаг АБАКР XVNRS V 3 шаг БДАКР XVNRS S 4 шаг БДАРК XVNRS N Как работает таблица подстановок?? Как меняются буквы АБДКР->АБАКР->БДАКР->БДАРК ?? XVNRS неизменяется?? Каким образом выбираются буквы X V S N??? Вобщем оч нужна ваше помощь! Заранее благодарен)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)