Шифрование информации

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

С₁ = Е_k1(T), С₂ = Е_k1(T), С₃ = Е_k1(T), ..., С_N = Е_k1(T), (9.4)

T = D_k2(C₁) = D_k2(C₂) = D_k2(C₃) = ... = D_k2(C_N). (9.5)

В результате, даже если у криптоаналитика имеется шифртекст C_i и он угадает T, то в результате операции шифрования получиться С_j = Е_k1(T). Вероятность того, что C_i = С_j крайне низка. Таким образом, криптоаналитик даже не узнает, была ли правильной его догадка относительно T или нет.

Ниже рассматриваются два алгоритма вероятностного шифрования:

- алгоритм шифрования Эль-Гамаля;

- алгоритм на основе эллиптических кривых.

4.4 Алгоритм шифрования Эль-Гамаля

Схема была предложена Тахером Эль-Гамаля в 1984 г. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и обеспечения аутентификации. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.

Суть задачи заключается в следующем. Имеется уравнение

g^x mod p = y. (6)

Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм).

Порядок создания ключей приводится в следующей таблице.

Таблица 8. Процедура создания ключей

Примечание. Первообразный (примитивный) корень по модулю p - наименьшее положительное число g такое, что g^(p) mod p = 1 и gⁱ mod p ? 1, для 1 ? i < (p), где (p) - функция Эйлера (т.к. р - простое число, то (p) = p - 1).

Проверка. При g = 2 и p = 37, (37) = 37 - 1 = 36.

2³⁶ mod 37 = 1;

2¹ mod 37 = 2 (? 1);

2² mod 37 = 4 (? 1);

2³ mod 37 = 8 (? 1);

2⁴ mod 37 = 16 (? 1);

...;

2³⁴ mod 37 = 28 (? 1);

2³⁵ mod 37 = 19 (? 1).

Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 < k < p - 1). После чего шифрограмма генерируется по следующим формулам

a = g^k mod p, (9.7)

b = (y^k Т) mod p, (9.8)

где Т - исходное сообщение;

(a, b) - зашифрованное сообщение.

Дешифрование сообщения выполняется по следующей формуле

T = (b (a^x)^-1) mod p (9.9)

или

T = (b a^p-1-x) mod p, (9.10)

где (a^x)^-1 - обратное значение числа a^x по модулю p.

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.

Первая часть шифрованного сообщения - a = 2⁷ mod 37 = 17.

a^x = 17⁵ = 1419857, (a^x)^-1 = 2 (1419857 * 2 mod 37 = 1) или a^p-1-x = 17^37-1-5 ? 1.3928892 * 10³⁸.



Таблица 9. Пример шифрования по алгоритму Эль-Гамаля (при k = const)

Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т'. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a', b') выполняется соотношение b (b')^-1 = Т (Т')^-1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т'.

Пример. Предположим злоумышленник перехватил зашифрованное сообщение С = ((a₁, b₁), (a₂, b₂), …, (a_n, b_n)), для которого использовалось одно и тоже случайное число k. Он знает один из блоков T_i = E_k1(C_i) или при известном открытом ключе (y, g, p) ему удалось подобрать k', которое совпало с используемым при шифровании k. Например по второму варианту, для шифрования символа Х (Т' = 22) злоумышленник использовал k' = 7 (равное k). Тогда, b(X) = b' = (32⁷ * 22) mod 37 = 11, (b')^-1 = 27, (Т')^-1 = 32. Расшифрование перехваченного сообщения приведено в следующей таблице.



Таблица 10. Пример расшифрования перехваченного сообщения

4.5 Алгоритм на основе эллиптических кривых

Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (Neal Koblitz) и Виктором Миллером (Victor Miller) в 1985 г. При использовании алгоритмов на эллиптических кривых полагается, что не существует быстрых алгоритмов для решения задачи дискретного логарифмирования в группах их точек. В настоящий момент известны лишь экспоненциальные алгоритмы вычисления обратных функций для эллиптических кривых. По сравнению с субэкспоненциальными алгоритмами разложения числа на простые сомножители (см. криптосистему RSA), это позволяет при одинаковом уровне стойкости уменьшить размерность ключа в несколько раз, а, следовательно, упростить программную и аппаратную реализацию криптосистем.

Эллиптической кривой E называется множество точек (x, y), удовлетворяющих однородному уравнению Вейерштрасса:

y² + a₁xy + a₂y = x³ + a₃x² + a₄x + a₅, (11)

где a_i - коэффициенты уравнения.



а) y² = x³ - x б) y² = x³ - 3x + 2

в) y² = x³ - x + 1

Рис. 6. Примеры эллиптических кривых

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (, где n > 3 - простое число) и полями характеристики 2 (GF(2^m)).

Эллиптические кривые над полями нечётной характеристики можно привести к виду, называемому эллиптической кривой в короткой форме Вейерштрасса:

y² = x³ + Ax + B (mod n), (12)

где A, B - коэффициенты эллиптической кривой, удовлетворяющие 4 A³ + 27 B² ? 0 (mod n).

Поскольку , график кривой симметричен относительно оси абсцисс. Чтобы найти точки его пересечения с осью абсцисс, необходимо решить кубическое уравнение



x³ + Ax + B = 0. (13)

Это можно сделать с помощью известных формул Кардано. Дискриминант этого уравнения

. (14)

Если ? > 0, то уравнение имеет три различных действительных корня (см. рис. 9.1а - x₁, x₂ и x₃). Если ? = 0, то уравнение имеет три действительных корня, по крайней мере, два из которых равны (см. рис. 9.1б - x₁ и x₂). Если ? = 0, то уравнение имеет один действительный корень (см. рис. 9.1в - x₁) и два комплексно сопряженных.

Используемые в криптографии кривые не должны иметь особых точек. Геометрически это значит, что график не должен иметь точек возврата и самопересечений (см. рис. 6б). Если кривая не имеет особых точек, то её график имеет две части при положительном дискриминанте (см. рис. 6а), и одну - при отрицательном (см. рис. 6в). Например, для графиков выше в первом случае дискриминант равен 64, а в третьем он равен -368.

Следует отметить, что в у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида P = (x, y) и -P = (x, -y). Например, эллиптическая кривая y² = x³ + 3x + 2 при x = 1 и n = 5 имеет две точки в качестве решения: P = (1, 1) и -P = (1, -1), т.к. 1² ? 1³ + 3 * 1 + 2 (mod 5) и (-1)² ? 1³ + 3 * 1 + 2 (mod 5).

Введем две операции, которые можно выполнять над точками кривой.

Сложение точек P₃(x₃, y₃) = P₁(x₁, y₁) + P₂(x₂, y₂).



а) y² = x³ - x б) y² = x³ - x + 1

Рис. 7. Сложение точек

(15)

(16)

В формулах 15 и 16 л - угловой коэффициент прямой, проходящей через точки P₁ и P₂. Если P₁ = P₂, то л равен значению производной в точке P₁.

Умножение точки на число P_k(x_k, y_k) = k * P(x, y).

а) y² = x³ - x б) y² = x³ - x + 1

Рис. 8. Удвоение точки



А) вариант 1 - выполнить сложение точки P k раз

(17)

B) вариант 2 - с использование двоичного представления числа k = (b_L, …, b₂, b₁) и операции удвоения точки. Например, k = 110 = (1101110)₂, тогда P_k = 64P + 32P + 8P + 4P + 2P.

Алгоритм, вычисления P_k может выглядеть следующим образом.

P_k = null, Q = P.

for i = 1 to L

If b_i = 1

then if P_k = null

then P_k = Q

else P_k = P_k + Q

Q = 2 * Q (? Q = Q + Q)

endFor

Для k = 110 вместо 109 сложений будет 1 присваивание, 4 сложения и 7 удвоений (сложений).

Рассмотрим процедуру создания ключей.



Таблица 11. Процедура создания ключей

Прямой способ вычисления порядка группы точек эллиптической кривой q.

1) Рассчитываются координаты первой точки из выражения

y² = x³ + Ax + B (mod n) > y² = x³ + 3x + 7 (mod 41).

Примем x₁ = 7, тогда y₁² mod 41 = (7³ + 3 * 7 + 7) mod 41 = 2, откуда y₁ = 17.

P(x_p, y_p) = P(x₁, y₁) = P(7, 17).

2) Находим координаты второй точки. Для этого вначале вычисляется коэффициент л



Решая последнее уравнение, получаем л = 2 (34 * 2 mod 41 = 27).

Координаты второй точки получаем путем удваивания первой из выражений

x₂ = (л² - 2x₁) mod n = (2² - 2 * 7) mod 41 = -10 mod 41 = 31,

y₂ = (л(x₁ - x₂) - y₁) mod n = (2 (7 - 31) - 17) mod 41 = -65 mod 41 = 17.

3) Каждую следующую точку рассчитываем по формулам, пока в знаменателе первой формулы не будет получен 0:

(18)

(19)

Получаем:

- л₃ = 0, x₃ = 3, y₃ = 24;

- л₄ = 29, x₄ = 11, y₄ = 31;

- л₅ = 24, x₅ = 25, y₅ = 2;

- …;

- л₄₆ = 2, x₄₆ = 7, y₄₆ = 24.

К полученному числу точек добавляем точку О, в результате чего q = 46 + 1 = 47. Эта точка есть результат сложения любых двух точек P(x_i, y_i) и -P(x_i, -y_i) и представляет собой бесконечно удаленную точку, в которой гипотетически сходятся все вертикальные кривые.

Процедура шифрования отдельного блока выполняется следующим образом.



Таблица 12. Процедура шифрования отдельного блока (буквы)

Процедура расшифрования отдельного блока выполняется следующим образом.

Таблица 13. Процедура расшифрования отдельного блока (буквы)

Приведенный выше способ шифрования является вариацией шифрования Эль-Гамаля. Если стойкость алгоритма шифрования Эль-Гамаля базируется на сложности решения задачи дискретного логарифмирования, то стойкость шифрования с помощью эллиптических кривых базируется на сложности нахождения множителя k точки P по их произведению. Т.е. если Q = k P, то зная P и k довольно легко вычислить Q. Эффективное решение обратной задачи (найти k при известных P и Q) на текущий момент пока не опубликовано.



Заключение

В ходе разработки и написания курсового проектирования был проведен анализ и изучение метода шифрования с открытым ключом. Так же были углублены знания относительно других методов шифрования и дешифрования.

Программа была разработана в среде Delphi 7, за счет чего программа обеспечивает быструю и качественную работу.



Список используемых источников

1. А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. Основы Криптографии. -- Гелиос АРВ, 2002 г.

2. Э. Мэйволд. Безопасность сетей. -- 2006 г.

3. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. -- М.: Вильямс, 2005 г.

4. Саломаа А. Криптография с открытым ключом. -- М.: Мир, 1995 г.

5. К. Шеннон. Теория связи в секретных системах // Работы по теории информации и кибернетике, 1963 г.

6. Жельников В. Кpиптогpафия от папиpуса до компьютеpа ,1996 г.

7. Бабаш А.В., Шанкин Г.П. История криптографии. Часть I, 2002 г.



Приложение

При старте программа выводит три окна: окно ввода текста для шифрования, окно для зашифрованного текста и окно для вывода расшифрованного текста.

Внешний вид окна ввода текста для шифрования

Внешний вид окна зашифрованного текста

Внешний вид окна для вывода расшифрованного текста



Листинг программы

unit Shifrovanie;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, IdCoder, IdCoder3to4, IdCoderUUE, IdCoderXXE, IdBaseComponent,

StdCtrls;

type

TForm1 = class(TForm)

mmo1: TMemo;

mmo2: TMemo;

btn1: TButton;

btn2: TButton;

idncdrx1: TIdEncoderXXE;

idcdrx1: TIdDecoderXXE;

mmo3: TMemo;

lbl1: TLabel;

Label1: TLabel;

lbl2: TLabel;

procedure btn1Click(Sender: TObject);

procedure btn2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.btn1Click(Sender: TObject);

begin

mmo2.Text:=idncdrx1.Encode(mmo1.Text) ;

end;

procedure TForm1.btn2Click(Sender: TObject);

begin

mmo3.Text:= idcdrx1.DecodeString(mmo2.Text) ;

end;

end.

Размещено на Allbest.ru