4.Ранцевый механизм. Создание открытого ключа по закрытому.
Рассмотрим работу алгоритма Меркла-Хеллмана.Алгоритм используется для преобразования сверхвозр.посл. для укладки ранца в нормальную.
Пример:
Пусть дана сверхвозр.посл. {2,3,6,13,27,52}. Умножим все члены данной послед.на число n по модулю m. Значение modm должно быть больше суммы всех членов послед. Допустим,пусть n=31,m=105
31 mod 105
2*31 mod 105 = 62
3*31 mod 105 = 93
6*31 mod 105 = 81
13*31 mod 105 = 88
27*31 mod 105 = 102
52*31 mod 105 = 37
Получили нормальную последовательность. {62,93,81,88,102,37}.
Сверхвозр.посл. – закрытый ключ, а нормальная – открытый.
Сообщение, представленное в двоичном виде, разбивается на блоки длиной равной кол-ву элементов в последовательности.
011000 110101 101110
011000 -> 93+81=174
110101 -> 62+93+88+37=280
101110 -> 62+81+88+102=333
Зашифрованное сообщение: {174,280,333}
Расшифровка. Получатель зашифрованного сообщения знает открытый и закрытый ключ, знает n и m. Для расшифровки текста необходимо найти значение: n-1 modm. После этого каждое значение шифр-текста умножается на (n-1)modm.
31-1 mod 105
31φ(105)-1 = 3147
105=3*31+12; 31=2*12+7 ;12=1*7+5; 7=1*5+2; 5=2*2+1; 2=2*1+0
31-1 mod 105=61
174*61 mod 105 = 9 mod 105
280*61 mod 105 = 70 mod 105
333*61 mod 105 = 48 mod 105
Для
9: {2,3,6,13,27,52}
Получили расшифрованное сообщение
011000
Для 70: 70>52 – да – берем;70-52=18
18>27 – нет;18>13 – да – берем;18-13=5
5>6 – нет; 5>3 – да –берем; 5-3=2
2=2 – берем
Получили сообщение 110101.
Для 48 аналогично получаем 101110
5. Открытое распределение ключей
До сих пор преимущества способов кодирования с открытым ключом не были абсолютно очевидными. Однако, на их основе достаточно просто решать вопрос выработки общего секретного шифра для сеанса взаимодействия любой пары пользователей информационной сети или системы.
Еще в 1976 году криптологи-теоретики Диффи и Хеллман изобрели для этих целей протокол открытого распределения ключей или шифров. Он подразумевает под собой взаимонезависимую генерацию каждым из пары обменивающихся информацией пользователей своего случайного символа, видоизменение его посредством некоторой операции, обмен видоизмененными числами по открытому каналу связи и определение общего секретного шифра на основе информации, переданной партнером в процессе связи.
Любой подобный ключ действителен всего лишь в течение одного сеанса связи или даже части такого сеанса. Соответственно, открытое распределение шифровальных ключей позволяет любой паре пользователей системы самостоятельно выработать свой общий шифровальный ключ, упрощая тем самым процедуру распределения секретных шифровальных ключей. Хотя далеко не все так просто - отсутствие у корреспондентов перед сеансом связи заблаговременно распределенного общего шифровального ключа вообще не даст им возможности убедиться в подлинности друг друга с помощью обмена сообщениями по открытому каналу.
Представим этот алгоритм обмена ключами такой последовательностью действий:
Алиса генерирует случ. число х, вычисляет число ax(mod p) и присылает его Бобу;
Боб генерирует случ. число в, вычисляет число aв(mod p) и присылает его Алисе;
Алиса і Боб вычисляют (aв(mod p))х = (aх(mod p))в = aху(mod p).
Число aху(mod p) используется в качестве ключа для симметричной криптосистемы. Здесь числа х і у шифруются с помощью необратимых функций соответственно ax(mod p) и aв(mod p), поэтому, перехватив при передаче числа ax(mod p) и aв(mod p) сложно получить секретный ключ (поскольку для этого необходимо получить одно из чисел х или у).
Алгоритм Диффи-Хэллмана обеспечивает конфиденциальность распределения, но не защищает от несанкционированной модификации секретного ключа во время распределения и не обеспечивает аутентичность корреспондента. Поэтому рекомендуется применять его (в таком виде) лишь тогда, когда нет возможности обеспечить безопасный обмен открытыми ключами. На практике широко применяется несколько модифицированный алгоритм Диффи-Хэллмана, который предусматривает, что параметры ax(mod p), aв(mod p) передаются вместе с их цифровой подписью. За счет этого можно обеспечить аутентичность этих параметров, но лишь в том случае, если абонентам предварительно удалось безопасно получить открытые ключи, необходимые для верификации цифровых подписей.
