Теоретическая часть. «криптоанализ шифра RSA»

ПРИ ВЫЧИСЛЕНИИ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ

ОПРЕДЕЛЕНИЕ ПОРЯДКА ВЫПОЛНЕНИЯ ОПЕРАЦИЙ

Лабораторная работа № 1

Лабораторная работа №7

«Криптоанализ шифра RSA»

Задание к лабораторной работе.

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

1. Проводит факторизацию N.

2. Определяет закрытый ключ.

3. Расшифровывает сообщение.

Варианты.

Вариант	(e,N)	C
7-1	(131,21733)
7-2	(137,25199)
7-3	(59,28829)
7-4	(59,29999)
7-5	(259,31921)
7-6	(251,33221)
7-7	(251,35909)
7-8	(251,37901)
7-9	(251,40349)
7-10	(251,42869)
7-11	(251,44923)
7-12	(251,46883)
7-13	(251,49583)
7-14	(251,50861)
7-15	(251,54053)
7-16	(251,56549)
7-17	(251,60479)
7-18	(251,61889)
7-19	(251,66043)
7-20	(251,70691)
7-21	(251,75137)
7-22	(251,77173)
7-23	(251,80851)
7-24	(251,83411)
7-25	(251,85073)

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

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

В процессе трансляции арифметические выражения преобразуют­ся в некоторую внутреннюю форму. Наиболее часто используется та­кое внутреннее представление арифметических выражений, как польская запись. Все формы внутреннего представления выражений, в том числе польская запись, содержат элементы двух видов - операторы и операнды. В простейшем случае операторы задаются зна­ками арифметических операций, такими как сложение "+", вычитание "-", умножение "*", деление "/", возведение в степень "^" и т.п. Операндами являются имена переменных и константы, над которыми выполняются указанные операции.

Любому арифметическому выражению можно поставить в соответ­ствие бинарное дерево, все конечные вершины (листья) которого со­ответствуют операндам, а внутренние вершины и корень - операто­рам. Например, дерево, описывающее арифметическое выражение

(a - b) * с + d / (e ^ f), (1)

имеет вид, показанный на рис. 1.

Рис. 1. Бинарное дерево для выражения (a - b) * с + d / (e ^ f)

Очевидно, что при представлении арифметического выражения в виде дерева не требуются скобки, так как приоритет соответствующих операций учитывается структурой дерева. Однако бинарное дерево не позволяет однозначно задать по­рядок выполнения некоторых промежуточных вычислений, необходимых для получения значения всего выражения. В частности, вычитание a - b можно выполнять раньше возведения в степень e ^ f, но допустимо и обратное.

Дата добавления: 2015-06-28