Асимметричные криптосистемы. Возможности и применение

1.

АСИММЕТРИЧНЫЕ
КРИПТОСИСТЕМЫ
Возможности и применение

2.

Схема связи

3.

Асимметричное
шифрование

4.

Односторонняя функция
где Кo – открытый ключ (для зашифрования),
Кs – секретный ключ (для расшифрования),
f – односторонняя (однонаправленная) функция, на
применении
которой
основаны
асимметричные
криптосистемы.
N=P*Q.

5.

Теория чисел
Основным понятием в арифметике остатков является
понятие модуля N (положительное натуральное число). Если
разность двух целых чисел (a-b) делится на N нацело, то
говорят, эти числа сравнимы по модулю N. В таком случае
используют запись вида:
Числа, сравнимые по модулю N образуют класс чисел по
модулю N. Всем числам класса отвечает один и тот же
остаток. Любое число класса называется вычетом по модулю
N по отношению ко всем числам класса (вычет – остаток от
целочисленного деления числа на модуль N).

6.

Наборы вычетов
• Максимальный набор чисел, взаимно простых с N,
называется приведённой системой вычетов по
модулю N. Приведенный набор вычетов вычисляется
путем выделения из полного набора вычетов чисел,
взаимнопростых с N.
• Пример 13: Пусть N=10
• Тогда полный набор вычетов будет выглядеть
следующим образом:
{0,1,2,3,4,5,6,7,8,9},
• а приведенный набор вычетов следующим образом:

7.

Взаимнопростые числа НОД (a,b)=1
• Наибольший общий делить можно найти с помощью
простого алгоритма Евклида

8.

• <?php
• echo "Взаимнопростые числа</br>";
• $n=39;$k=0;
• for ($d=1; $d < $n; $d++)
{
if (($d % 3 == 0) or ($d % 13 == 0));
else { echo "$d"; echo "</br>"; $k++; }
}
echo "k=";
echo "$k"
?>

9.

НОД (4848, 1212)
• <?php
• echo "</br>";
• echo 'НОД(4848;1212)';
• echo "</br>";
• $a = 4848;
• $b = 1212;
• while ($b!=0)
•{
• $r=$a%$b; $a=$b; $b=$r;
•}
• echo " НОД= $a";
• ?>

10.

Теория чисел
Обратным к числу a по модулю m можно назвать такое число
b, которое удовлетворяет условию: