Реферат: Криптографические системы

Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме 1.

Под результатом операции i mod j будем понимать остаток от целочисленного деления i на j.

Наиболее важной частью алгоритма RSA, как и других алгоритмов с открытым ключем, является процесс создания пары открытый/секретный ключи. В RSA он состоит из следующих шагов.

1. Случайным образом выбираются два секретных простых числа, p и q, p¹q.

2. Вычисляется r=p*q.

3. Вычисляется f=(p-1)*(q-1).

4. Выбираются открытый (Ко) и секретный (Кс) ключи, которые являются взаимно простыми с f и удовлетворяют условию (Ко*Кс) mod f = 1.

Чтобы зашифровать данные открытым ключем Ко, необходимо:

1) разбить исходный текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, ..., n-1;

2) зашифровать последовательность чисел M(i) по формуле

C(i)=(M(i)Ко) mod n,

где последовательность чисел C(i) представляет шифротекст.

Чтобы расшифровать эти данные секретным ключем Кс, необходимо выполнить следующие вычисления:

M(i)=(C(i)Кс) mod n.

В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Приведем простой пример использования метода RSA для шифрования сообщения “CAB”. Для простоты будем использовать малые числа (на практике используются намного большие числа).

1. Выберем p=3, q=11.

2. Вычислим r=3*11=33.

3. Вычислим f=(p-1)*(q-1)=20.

4. Выберем секретный ключ Кс, который является взаимно простым с f, например Кс=3.

5. На основе Кс и f вычислим открытый ключ Ко. Для этого можно использовать расширение алгоритма Евклида:

BEGIN

g0=f; g1=Kc;

u0=1; u1=0;

v0=0; v1=1;

i=1;

while g_i ¹0 do

begin

g_i= u_i f+v_i Kc;