X1

X2

X3 X4

Transformation

Z1…Z4

Раунд №1

I11

I12

I13

I14

Sub ciphering

Z5Z6

W11 W12 W13

W14

…

Р

W71 W72 W73 W74

Transformation

Z43…Z46

Раунд №8

I81

I82

I83

I84

У

Sub ciphering

Z47Z48

И

W81 W82 W83

W84

Output Transformation

Z49…Z52

Г

Y1

Y2

Y3

Y4

ритма

Рис. 11. Порядок использов нияБитерационных

к

IDEA

ключей алго

При выполнении дешифрованияЗначенияраунды алгоритма выполняются в таком

же порядке. На вход первого раунда подаётся четыре 16-битных подблока ходного раунда, являются подблоками 64-битного блока исходного текста. От-

64-битного блока шифро екс а. , полученные после выполнения вы-

личие от процедуры					вания заключается в том, что вместо ключей Z1...Z52
используются ключи U1				...U52т.
			о			Задания
	шифр
1. Разра отать программное средство, выполняющее шифрование по ал-
горитму IDEA заданного файла с произвольным содержимым. Ключ шифрова-
	л
ния подаётся в виде бинарного файла длиной 16 байт.
2. Разработатьб		программное средство, выполняющее дешифрование за-
данного файла, зашифрованного по алгоритму IDEA. Ключ шифрования пода-
и
ется в виде бинарного файла длиной 16 байт.
Б

21

Алгоритм сложения

5. АРИФМЕТИКА ЧИСЕЛ БОЛЬШОЙ РАЗРЯДНОСТИ

Размерность обрабатываемых в вычислительных машинах чисел обычно ограничивается размерностью машинного слова. Типичная переменная целочисленного типа занимает в памяти машины 8, 16, 32 или 64 бит. Для многих криптографических алгоритмов требуются числа намного большего размера. Например, рекомендуемый размер открытого ключа для алгоритма RSA составляет 4 Кбит. Рассмотрим реализацию базовых арифметических операций

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

над целыми числами большого размера. Для представления цифрРбольших чи-

Алгоритм сложения неотрицательных чисел достаточноУИпрост: цифры

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

числа складываются, начиная с младших разрядов к старшим. Если зафиксиро-

следующий разряд.			Рассмотрим реализацию сложения неотрицательных
n-разрядных целых чисел (un-1, …, u0)b и (vn-1, …,Бv0)b по основанию b. Следую-
щий алгоритм формирует их сумму (wn, wn-1, …, w0)b, причем wn {0, 1}:
							а
ADD(u, v, n)						к
j := 0; k := 0;
while j < n
					е
do wj := uj + vj + k
	if wj ≥ b
		then wj := wj			– b
		k	:= 1	т
		else kо:= 0
	j := j + 1
wn := k		и
return (wn, …, w0)
	л
Замет м, что при работе этого алгоритма всегда выполняются соотноше-
б
ния uj + vj + k ≤ (b – 1) + (b – 1) + 1 < 2b, так что размер результата суммирова-
ния неипревышает log22b = b + 1 разрядов. Приведенный алгоритм может ис-

пользоватьсяБ и для сложения отрицательных чисел. Для этого следует использовать их представление в дополнительном коде.

Алгоритм умножения

Умножение больших чисел может быть выполнено традиционным школьным способом «в столбик». Однако вместо использования массива про-

22

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

Если множимое состоит из m слов, множитель – из n слов, то произведение занимает не более m + n слов, независимо от того, выполняется знаковое или беззнаковое умножение. Рассмотрим реализацию умножения неотрицательных целых чисел (um-1, …, u0)b и (vn-1, …, v0)b по основанию b. Следующий алгоритм формирует их произведение (wm + n – 1, …, w0)b:

MULTIPLY (w, v, m, n)

for j = 0, …, m – 1 do wj := 0;

Р

j := 0;

while j < n

do if vj > 0

then i := 0; k := 0;

while i < m

И

do t := ui ∙ vj + wi+j + k:

wi+j := t mod b;

У

k := t/b ;

Г

i := i + l;

else

wj + m := k;

Б

wj + m := 0;

j := j + l;

а

return (wm + n - 1, …,w0)

На каждом шаге алгоритма умнож ния выполняются неравенства

к

0 ≤ t < b2, 0 ≤ k < b.

е

Умножение больших чисел выполняется проще для беззнаковых операн-

дов. Знак

произведения

получается

как

результат операции

«ИСКЛЮЧАЮЩЕЕ-ИЛИ» над разрядами знака множителей.

т

Умножение целых ч сел может быть существенно ускорено. Например,

n

U1

оn

пусть u = b

+ U0, v = b V1

+ V0. Тогда (алгоритм Карацубы)

и

2n

n

+ b (U1V0 + U0V1) + U0V0 =

uv = b U1V1

= b2nU1V1 + bn((U0 + V0)(U1 + V1) – U0V0 – U1V1) + U0V0 =

л

= b2nC0 + bn(С2 – С1 – С0) + С1,

(11)

б

U0V0, С2 = (U0

+ V0)(U1 + V1).

где С0 = U1V1,

С1 =

Алгоритм

Карацубы сводит задачу умножения двух чисел к нескольким

Б

задачам умножения чисел меньшей разрядности. Разбиение может осуществляться рекурсивно до тех пор, пока разрядность не уменьшится до поддерживаемой аппаратно (т.е. пока n не достигнет размера машинного слова). В этом случае число элементарных умножений для алгоритма Карацубы асимптотически сходится к O(nlog2 3).

Пример: 13 ∙ 27 = 100 ∙ 1 ∙ 2 + 10 ∙ (3 ∙ 7 + 1 ∙ 2) + 3 ∙ 7 = 100 ∙ 2 + 10 ∙ (36 –

– 21 – 2) + 21 = 200 + 130 + 21 = 351.

23

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

Деление

Основная сложность при реализации классического метода деления «в столбик» состоит в необходимости угадывать разряды частного на каждой итерации алгоритма. Этот процесс должен быть формализован. Прежде всего заметим, что деление т-разрядного числа на п-разрядное (т > п) сводится к по-

следовательности делений (п + 1)-разрядных чисел и на n-разрядное число v,
причем 0 ≤ u/v < b, где b –	Р
	основание системы счисления. Таким образом, необ-

(un, un-1, …, u1)b < v = (vn, vn-1, …, v0)b. Частное q должно быть единственным це-

ходимо построить алгоритм для нахождения q = u/v , u = (un, un-1, …, u0)b и
v = (vn, vn-1, …, v0)b.			И
Условие u/v < b может быть переформулированоУкак и/b < v, т. е.
	Г
	Б

			а
лым числом, таким, что 0 ≤ и – qv < v. Попытаемся угадать q как
q* min	к					,b 1 .		(12)
	unb		un 1
		v
е				n 1
В данном случае q* q, при этом					сли q* превышает q,			то превышение
незначительно. Кроме того, если vn-1		≥ b/2 , то					q* 2 q q*. Это условие

носит название условия нормализации. Его можно обеспечить, домножив де-

лимое и делитель на						b/ vn 1	1 .	Дополнительно можно показать, что если
				и
q*vn 2 br * un 2 , то						q* < qт, где r* = uпb + un–1 + q*vn–1. В противном случае
q { q*, q* – 1}.						о		алгоритм вычисления частного m и остатка
Исходя из эт					х соображений,
	б
n от деления (um+n-1, …, u0)b на (vn-1, …, v0)b имеет вид
л
DIVIDE(u, v, m, n)
d :=		b/(v			1)	;
Б			n 1
(um+n, um+n-1, …, u0)b := d ∙ (um+n-1, …, u0)b
и(vn-1, …, v0)b := d ∙ (vn-1, …, v0)b
j := m
while j ≥ 0

do q*: (uj nb uj n 1)/vn 1 r*: (uj nb uj n 1)modvn 1

if (q* b) (q*vn 2 br * uj n 2 ) then q*: q* 1

24