Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
79
ГЛАВА 5 числа N(i). Число N(і), лимитирующее сверху допустимый объем каждого передаваемого фрагмента текста (независимо от того, является ли этот текст архивированным или нет), зависит от того, насколько большими выбраны числа q(i) и p(i). Например, если числа q(i) и p(i) содержат по 100 десятичных знаков каждое, то число N (і) будет состоять из 200 десятичных знаков, что эквивалентно 660 битам, т.е. при таком выборе чисел q(i) и p(i) объем каждого фрагмента шифруемого текста сверху лимитирован 660 битами.
В качестве односторонней функции с ловушкой в системе RSA служит функция
у = /(Ar) = Ar^mod (N(i)). (4.7)
Эта функция признается односторонней в силу того, что пока не известны результаты, позволяющие при достаточно больших числах e(i) и N(i) на основе числа у (т.е. на основе криптограммы) определить число X (т.е. исходное сообщение). Иными словами, при заданном аргументе X вычисление у = /(Ar) не представляет особого труда, тогда как обращение функции /(Ar), т.е. вычисление значения
X=J4(V) (4.8)
при известном у связано с большим объмом вычислительных работ. Заметим, что утверждение об отсутствии эффективных методов обращения функции (4.7), равно как и утверждение об отсутствии эффективных методов разложения больших чисел N(і) на простые множители <7(0 и p(i)tскорее являются предположениями, нежели утверждениями в строгом математическом смысле. По крайней мере, нам не известны публикации, где бы приводилось доказательство этих предположений, которые скорее строятся не на строгих доказательствах, а лишь на отсутствии работ, где бы приводились эффективные методы обращения функции (4.7) или разложения числа N(і) на простые множители. Это обстоятельство является одной из слабых сторон, присущих всем криптосистемам открытого шифрования, базирующихся на возведении чисел в большие степени по большому модулю.
Несмотря на вышесказанное, в дальнейшем изложении мы все же будем придерживаться предположения о том, что обращение функции (4.7), равно как и разложение чисел N(і) на простые множители, представляются достаточно сложными задачами и поэтому перехват злоумышленником числа у не позволит ему восстановить конфиденциальное сообщение X. В этом, собственно, и заключается односторонность функции (4.7). Что же касается ловушки для этой функции, то ее роль в данном случае выполняет секретный ключ d(i), поскольку с его помощью обращение функции (4.7) существенно упрощается. Так, легко
80 убедиться, что имеет место
/«¦!) mod(/V(0) = XeliM)mod(N(i)) = (4.9)
= Xl+tw<''»mod(/V(0) = X ¦ Xiiw"»mod(N(i)).
Если X является взаимно простым с N(i) числом, то согласно теореме Эйлера
XpwCO=Imod (/V(Z)) (4.10)
и поэтому с учетом (4.9) имеем
X = /('>mod(/V(0). (4.11)
Можно, однако, доказать, что соотношение (4.11) имеет место для любого X < N (і), независимо от того, является ли X взаимно простым с числом N(i) или нет, т.е. независимо от того, имеет ли место формула (4.10) или нет. Во всех случаях число
Xp^mod(NU))
является единичным элементом некоторой группы относительно операции умножения - группы, которой принадлежит элемент X. А это означает, что при любых X < N(і) формулу (4.9) можно переписать как
y/("mod(/V(O) =XE mod(/V(0) = X, (4.12)
где E единый элемент группы, которой принадлежит элемент X. Иными словами, абонент, владеющий секретным ключом d(i), с помощью формулы
X = /-'(у) = /Mmod(NU)) (4.13)
относительно легко восстановит исходное сообщение X, расшифровывая тем самым криптограмму у.
В этом, собственно, и заключается сущность криптосистемы RSA, где шифрование исходных сообщений X осуществляется с использованием открытого ключа - пары чисел e(i) и N(i) и сводится к вычислению криптограммы у с помощью формулы (4.7). Расшифрование криптограммы у осуществляется с использованием секретного ключа -числа d(i) и сводится к вычислению исходного сообщения X с помощью формулы (4.11). Пример 4. L
Пусть в качестве простых чисел q(i) и /?(/) выбраны числа q(i) = 17 и /?(/) = 23. Тогда N(i) = 17 ¦ 23 = 391, а число F(N(i)) определится по формуле (4.5), т.е.
F(N(i)) = 16- 22 = 352 = 25 • И. В качестве e(i) при этом можно брать произвольное взаимно простое с
81
ГЛАВА 5 F(N(i)) число, например, число e(i) = 85. Тогда в качестве числа d(i) можно выбрать произвольное число, удовлетворяющее условию (4.6), например, число d(i) = 29. Легко проверить, что пара чисел e(i) = 85 и d(i) = 29 удовлетворяет условию (4.6). Очередным конфиденциальным сообщением может служить произвольное число X, удовлетворяющее условию
2 == X =S N(i) - 2
(обратим внимание, что из интервала возможных значений X мы исключили числа X=IhX =N(i) - 1). Пусть X = 35. Тогда шифрограммой будет служить число
у = 3585mod(391) = 307.
Именно число у = 307 и посылается по открытому каналу связи в адрес /-го абонемента - получателя информации. Чтобы восстановить исходное сообщение, т.е. число X, і-й абонент возводит число у = 307 в степень d(i) = 29 по тому же модулю N(i) = 391:
X = 30729mod(391) = 35.
