Основные принципы несимметричных алгоритмов. Алгоритм упаковки рюкзака

Принцип несимметричных алгоритмов шифрования применяется для создания электронной цифровой подписи (ЭЦП).
Электронно-цифровая подпись позволяет:
- подтвердить авторство электронного документа;
- подтвердить подлинность и время подписи электронного документа.

В Интернете используют несимметричные криптографические системы, основанные на использовании не одного, а двух ключей. Происходит это следующим образом. Компания для работы с клиентами создает два ключа: один - открытый (public - публичный) ключ, а другой - закрытый (private - личный) ключ. На самом деле это как бы две "половинки" одного целого ключа, связанные друг с другом.

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

Как публичный, так и закрытый ключ представляют собой некую кодовую последовательность. Публичный ключ компании может быть опубликован на ее сервере, откуда каждый желающий может его получить. Если клиент хочет сделать фирме заказ, он возьмет ее публичный ключ и с его помощью закодирует свое сообщение о заказе и данные о своей кредитной карте. После кодирования это сообщение может прочесть только владелец закрытого ключа. Никто из участников цепочки, по которой пересылается информация, не в состоянии это сделать. Даже сам отправитель не может прочитать собственное сообщение, хотя ему хорошо известно содержание. Лишь получатель сможет прочесть сообщение, поскольку только у него есть закрытый ключ, дополняющий использованный публичный ключ.

Основные понятия:

{KO,KR} – пара ключей (открытый и секретный);

M – исходное (нешифрованное) сообщение (число);

ЕKO(.) – алгоритм шифрования;

DKR(.) – алгоритм дешифрования;

А --------->???>----------> B

KOB {KOB, KRB}

C=EKOB(M)-> C >-->P= DKRB(C)

C = ЕKO(M) – зашифрованное сообщение (по открытому каналу).

Алгоритмы ЕKO(.), DKR(.) и открытый ключ KO – известны (!).

Секретом является только закрытый ключ KR!

Дополнительным (к тем, что типичны для симметричных алг.) требованием является трудность определения KR по известному KO.

Характеристика несимметричных алгоритмов (НА)по сравнению с симметричными (СА):

Ø Относительно бо’льшая вычислительная трудоемкость НА

Ø Бо’льшая длина ключа НА (~ в 10 раз)

Практическое применение:

1. цифровая подпись (в дальнейшем).

2. передача секретного ключа СА, вместо шифрования всего текста (использование в комбинации с СА, например, в системе PGP)

Алгоритм Рюкзака

Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разработанный Ральфом Мерклом и Мартином Хеллманом.

Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению? Более формально, дан набор значений M₁, М₂,..., М_n и сумма S, вычислить значения b_i, такие что

S = b₁М₁+ b₂М₂+...+ b_пМ_п

b_i может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут.

Например, массы предметов могут иметь значения 1, 5, 6, 11, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11.

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

В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать сообщение как решение набора проблем рюкзака. Предметы из кучи выбираются с помощью блока открытого текста, по длине равного количеству предметов в куче (биты открытого текста соответствуют значениям b), а шифротекст является полученной суммой. Пример шифротекста, зашифрованного с помощью проблемы рюкзака.

Шифрование с рюкзаками

Открытый текст
Рюкзак	1 5 6 11 14 20	1 5 6 11 14 20	1 5 6 11 14 20	1 5 6 11 14 20
Шифротекст	1+5+6+20=32	5+11+14=30	0=0	5+6=11

Фокус в том, что на самом деле существуют две различные проблемы рюкзака, одна решается за линейное время, а другая, как считается, - нет. Легкую проблему можно превратить в трудную. Открытый ключ представляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для дешифрирования сообщений. Закрытый ключ является легкой проблемой, давая простой способ дешифрировать сообщения. Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака.

Алгоритм RSA

RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация – установление подлинности). (1977, разработчики Ronald Rivest, Adi Shamir и Leonard Adleman).

Его проще всего понять и реализовать. Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытые ключи являются функциями двух больших (100-200 разрядов или даже больше) простых чисел.

Для генерации двух ключей используется два больших случайных числа, p и q. Для максимальной безопасности выбираются p и q равной длины. Рассчитывается произведение:

N=p*q.

Затем случайным образом выбирается ключ шифрования e, такой что e и (p-1)(q-1) является взаимно простыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифрирования d, такого что ed=1(mod(p-1)(q-1))

c – зашифрованное сообщение

Использование криптосистемы RSA в настоящее время

Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

Алгоритм Эль Гамаля

Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = g^k mod p. Далее из уравнения M = (xa + kb) mod (p-1) находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число k следует хранить в секрете. Для верификации подписи необходимо проверить равенство:

y^aa^b mod p = g^M mod p.

Пара a и b представляют собой зашифрованный текст. Следует заметить, что зашифрованный текст имеет размер в два раза больше исходного. Для дешифрования производится вычисление:

M = b/a^x mod p

13. Электронная подпись. Основные понятия и принципы формирования.

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

Принцип: Это так называемая система криптографического преобразования с симметричным ключом. Она предполагает наличие одного закрытого ключа как у Отправителя, так и у Получателя. Отправитель на закрытом ключе Ks зашифровывает передаваемое сообщение M с помощью определенного криптографического алгоритма и, в зашифрованном виде, отправляет его Получателю. Алгоритм криптографического преобразования определяется соответствующим стандартом. Получатель с помощью точно таких же закрытого ключа Ks и криптографического алгоритма расшифровывает (восстанавливает) принятое шифрованное сообщение M(K). Такая криптосистема обладает хорошей устойчивостью к дешифрованию. Недостаток такой криптосистемы в том, что закрытым ключом владеют минимум два человека, при компрометации ключа у одного из них, компрометируется вся система в целом. Это приводит также к тому, что в такой криптографической системе невозможно определить, кто ответственен за компрометацию закрытого ключа.

В отличие от криптографической системы с симметричным ключом, в системе с асимметричными ключами зашифрование и расшифрование осуществляются на разных, математически связанных (парных) ключах. В такой системе Отправитель изготавливает себе ключевую пару - закрытый Ks и открытый Kp ключи. Закрытый ключ Ks остается у отправителя, открытый Kp передается всем получателям. Сообщение, зашифрованное на закрытом ключе Ks, может быть расшифровано только на открытом ключе Kp:

Таким образом, в этой криптографической системе закрытым ключом Ks владеет только один человек. Соответственно, так зашифровать сообщение M, что оно будет расшифровано с помощью парного открытого ключа Kp, может только владелец закрытого ключа Ks. Алгоритмы асимметричного криптографического преобразования также стандартизированы. Главным достоинством такой системы является владение закрытым ключом Ks только одного человека и его единоличная ответственность за компрометацию этого ключа. Недостаток этой системы - сложность алгоритмов, что снижает скорость криптографического преобразования.

Свойство криптографической системы с асимметричными ключами предоставлять закрытый ключ Ks только одному человеку используется для формирования реквизита электронного документа - электронной цифровой подписи.

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

Проверка электронной цифровой подписи производится с использованием парного открытого ключа Kp. Механизм проверки представлен на рисунке ниже:

Назначение ЭЦП.

Электронная цифровая подпись может иметь следующее назначение:

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

Защиту от изменений (подделки) документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев.

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

Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.

Электронная подпись RSA

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

расшифровки хэша, сам рассчитывает хэш для сообщения, и сравнивает эти два хэша.

Описание алгоритма: Безопасность алгоритма электронной подписи RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа -- открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для зашифровывания данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно

N=p*q.

c – зашифрованное сообщение