Дешифрование

Генерация ключей

1. Генерируется случайное простое число длины битов.

2. Выбирается случайный примитивный элемент поля .

3. Выбирается случайное целое число такое, что .

4. Вычисляется .

5. Открытым ключом является тройка , закрытым ключом — число .

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование

Сообщение шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число такое, что

2. Вычисляются числа и .

3. Пара чисел является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.

Дешифрование

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

При этом нетрудно проверить, что

и поэтому

.

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

Билет 3

1 Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называетсяэнтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятностидвухбуквенных сочетаний):

где i — это состояние, зависящее от предшествующего символа, и p_i (j) — это вероятность j, при условии, что i был предыдущим символом.

Так, для русского языка без буквы «ё» .

Через частную и общую условные энтропии полностью описываются информационные потери при передачеданных в канале с помехами. Для этого применяются так называемые канальные матрицы. Так, дляописания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условнуювероятность получения приёмником символа b_j при условии, что был отправлен символ a_i. Приэтом канальная матрица имеет следующий вид:

	b 1	b 2	…	bj	…	bm
a 1			…		…
a 2			…		…
…	…	…	…	…	…	…
ai			…		…
…	…	…	…	…	…	…
am			…		…

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а суммавсех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника — p (b_j). Потери, приходящиеся на передаваемый сигнал a_i, описываются через частную условную энтропию:

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можнополучить p (a_i), а элементы диагонали означают вероятность того, что был отправлен именно тот символ,который получен, то есть вероятность правильной передачи).

2 Шифрование и дешифрование

Как шифрование, так и дешифрование в RSA предполагает использование операции

возведения целого числа в целую степень по модулю n. Если возведение в степень выпол-

нять непосредственно с целыми числами и только потом проводить сравнение по модулю

n, то промежуточные значения окажутся просто огромными. К счастью, здесь можно вос-

пользоваться свойствами арифметики в классах вычетов:

[(a mod n) × (b mod n)] mod n = (a × b) mod n.

Таким образом, мы можем рассматривать промежуточные результаты по модулю n. Это

делает вычисления практически возможными.

Другой проблемой является эффективная реализация операции возведения в степень,

так как в случае применения RSA мы должны иметь дело с потенциально большими пока-

зателями. Чтобы продемонстрировать, насколько здесь можно увеличить эффективность

вычислений, предположим, что необходимо вычислить x¹⁶. Прямолинейный подход потребует 15 умножений, как показано ниже.

x¹⁶ = x × x × x × x × x × x × x × x × x × x × x × x × x × x × x × x

Однако такого же конечного результата можно достичь и с помощью всего четырех умно-

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

x², x⁴, x⁸, x¹⁶.

В общем случае предположим, что нам нужно найти значение a^m, где a и m являются положительными целыми числами. Если представить m в виде двоичного числа b_kb_k−1 … b₀, то

m=

и поэтому

Билет 4

Взаимная энтропия, или энтропия объединения, предназначена для рассчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (AB), где A, как всегда, характеризует передатчик, а B — приёмник.

Взаимосязь переданных и полученных сигналов описывается вероятностями совместных событий p (a_ib_j), и для полного описания характеристик канала требуется только одна матрица:

p (a 1 b 1)	p (a 1 b 2)	…	p (aibj)	…	p (a 1 bm)
p (a 2 b 1)	p (a 2 b 2)	…	p (a 2 bj)	…	p (a 2 bm)
…	…	…	…	…	…
p (aib 1)	p (aib 2)	…	p (aibj)	…	p (aibm)
…	…	…	…	…	…
p (amb 1)	p (amb 2)	…	p (ambj)	…	p (ambm)

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p (b_j), сумма строки с номером i есть p (a_i), а сумма всех элементов матрицы равна 1. Совместная вероятность p (a_ib_j) событий a_i и b_j вычисляется как произведение исходной и условной вероятности,

p (a_ib_j) = p (a_i) p (b_j | a_i) = p (b_j) p (a_i | b_j).

Условные вероятности производятся по формуле Байеса. Таким образом имеются все данные для вычисления энтропий источника и приёмника:

Взаимная энтропия вычисляется последовательным суммированием по строкам (или по столбцам) всех вероятностей матрицы, умноженных на их логарифм:

H (AB) = −	∑	∑	p (aibj)log p (aibj)
	i	j

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов — отправленного и полученного. Путём несложных преобразований также получаем

H (AB) = H (A) + H (B | A) = H (B) + H (A | B).

Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины

2 Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разработанный Ральфом Мерклом и Мартином Хеллманом. Он мог быть использован только для шифрования, хотя позднее Ади Шамир адаптировал систему для цифровой подписи. Безопасность алгоритмов рюкзака опирается на проблему рюкзака, NP-полную проблему. Хотя позже было обнаружено, что этот алгоритм небезопасен, его стоит изучить, так как он демонстрирует возможность применения NP-полной проблемы в криптографии с открытыми ключами.

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

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

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

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

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

Билет 5

1 Из энтропийных оценок источников сообщений, ясно, что она зависит от статических характеристик самих сообщений. Энтропия максимальна при равномерном появлении букв на любом месте сообщения. Для характеристики источника сообщений с различным алфавитом представляет интерес сравнение фактической энтропии источника с максимально возможной. В этом смысле введено понятие избыточности источника сообщений или избыточности алфавита.

,

где H _max = log M;

M – количество различных букв в алфавите;

H (X) – средняя энтропия на одну букву.

Избыточность источника R показывает на сколько хорошо используются буквы в данном источнике. Чем меньше R, тем большее количество информации вырабатывается источником на одну букву. Однако, не всегда необходимо стремиться к R = 0. С повышением избыточности повышается помехоустойчивость (надежность) источника. Выяснение количества избыточности важно потому, что мы должны вводить ее разумно, чтобы получить максимальный эффект помехозащищенности, а не полагаться на стихию. Например, избыточность любого языка оказывается порядка 50-70%, то есть если бы все буквы имели одинаковую вероятность использования и можно было бы использовать любые комбинации букв, то среднюю длину слова можно было бы значительно уменьшить. Однако разбираться в этой записи было бы значительно труднее, особенно при наличии ошибок (лектора или студента).

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

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

2 На данный момент асимметричное шифрование на основе открытого ключа RSA (расшифровывается, как Rivest, Shamir and Aldeman - создатели алгоритма) использует большинство продуктов на рынке информационной безопасности.

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

Рассмотрим алгоритм RSA с практической точки зрения.

Для начала необходимо сгенерировать открытый и секретные ключи:

§ Возьмем два больших простых числа p and q.

§ Определим n, как результат умножения p on q (n= p*q).

§ Выберем случайное число, которое назовем d. Это число должно быть взаимно простым (не иметь ни одного общего делителя, кроме 1) с результатом умножения (p-1)*(q-1).

§ Определим такое число е, для которого является истинным следующее соотношение (e*d) mod ((p-1)*(q-1))=1.

§ Hазовем открытым ключем числа e и n, а секретным - d и n.

Для того, чтобы зашифровать данные по открытому ключу {e,n}, необходимо следующее:

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

§ зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле C(i)=(M(I)^e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

3 задача

Билет 6

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

Условной вероятностью (два обозначения) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.

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

.

В частности, отсюда получаем
.

2 Коды Хэмминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.

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

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

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

Билет 7

1 Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

Линейный код называют циклическим, если для любого кодового слова [x_nx₀x₁...x_n-1] циклическая перестановка символов [x₀x₁...x_n-1x_n] также дает кодовое слово.

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

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

Принято описывать циклические коды (ЦК) при помощи порождающих полиномов G(Х) степени m = n – k, где m – число проверочных символов в кодовом слове. В связи с этим ЦК относятся к разновидности полиномиальных кодов.

Операции кодирования и декодирования ЦК сводятся к известным процедурам умножения и деления полиномов. Для двоичных кодов эти операции легко реализуются технически с помощью линейных переключательных схем (ЛПС), при этом получаются относительно простые схемы кодеков, в чем состоит одно из практических достоинств ЦК.

Среди циклических кодов особое место занимает класс кодов, предложенных Боузом и Чоудхури и независимо от них Хоквингемом. Коды Боуза-Чоудхури-Хоквингема получили сокращенное наименование БЧХ-коды. БЧХ-коды являются обобщением кодов Хемминга на случай исправления нескольких независимых ошибок (gи > 1). Частными случаями БЧХ- кодов являются коды Файра, предназначенные для обнаружения и исправления серийных ошибок («пачек» ошибок), код Голея – код, исправляющий одиночные, двойные и тройные ошибки (dmin= 7), коды Рида–Соломона (РС-коды), у которых символами кода являются многоразрядные двоичные числа.

2 Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи(ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

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

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

Алгоритмы криптосистемы с открытым ключом можно использовать

· как самостоятельное средство для защиты передаваемой и хранимой информации,

· как средство распределения ключей (обычно с помощью алгоритмов криптосистем с открытым ключом распределяют ключи, малые по объёму, а саму передачу больших информационных потоков осуществляют с помощью других алгоритмов),

· как средство аутентификации пользователей.

Дата добавления: 2015-08-13