Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17




НазваниеСодержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17
страница78/78
Дата конвертации11.12.2012
Размер5.58 Mb.
ТипРеферат
1   ...   70   71   72   73   74   75   76   77   78

Модульная арифметика


Описанная система шифрования с открытым ключом основана на математической концепции, известной как модульная арифметика (modular arithmetic), или модульная система. Эта система получается путем замены каждого целого числа из традиционной арифметической системы остатком, образующимся при делении этого числа на предопределенное значение. Предопределенное значение называется модулем. Например, пусть модуль равен 7, тогда целые значения О 1 2 3 4 5 6 7 8 9 ... будут преобразованы в значения О 1 2 3 4 5 6 0 1 2 ...

Для обозначения остатка, полученного при делении х на т, обычно используется сокращение х (mod m), которое читается как «х по модулю от» или иногда просто «к модуль от». Так, 9 (mod 7) равно 2, так как остаток от деления 9 на 7 равен 2. Аналогично, 24 (mod 7) равно 3, потому что при делении 24 на 7 получается остаток 3; а 5 (mod 7) равно 5.

Два целых числа, которые при делении на т дают одинаковый остаток, называются эквивалентными по модулю т. Так, 16 и 23 эквивалентны по модулю 7, так как 16 (mod 7) = 23 (mod 7). Действительно, при делении на 7 и значение 16, и 23 дают остаток 2. Для обозначения того, что значение х эквивалентно у по модулю т часто используется сокращение х = у (mod от). Так, 16 = 23 (mod 7).

После преобразования обычных целых значений в модульную систему по модулю от у нас остаются только значения 0, 1, 2, 3, ..., от - 1. Мы можем выполнять арифметические операции в пределах ограниченного набора чисел; для этого операция сначала выполняется так же, как в традиционной арифметике, а затем ответ, предположим, х, переводится обратно в ограниченный диапазон путем замены его на значение х (mod m). Так, в модульной системе по модулю 7 у нас есть только значения 0, 1, 2, 3, 4, 5 и 6. При сложении 2 + 6 мы получим значение 1, так как 2 + 6 = 8, что при делении на 7 дает в остатке 1. Результатом умножения 2x6 будет 5, так как 2x6= 12, а при делении на 7 остаток равен 5.

Арифметика в модульной системе — это искаженное отражение арифметики в традиционной системе. Она является отражением в том смысле, что если х = a (mod rri) и у = Ъ (mod т), то х + у = а + Ъ (mod m). А искажение означает, что суммы и произведения в двух системах не равны. В частности, произведение двух различных целых чисел в модульной системе может быть равно 1, что ни при каких условиях невозможно в традиционной системе целых чисел. Например, в системе по модулю 7 мы имеем 3x5 = 1 (так как 3x5= 15, а 15 -н 7 в остатке дает 1).

Два числа, которые при умножении дают 1, называются мультипликативными инверсиями друг друга. В традиционной системе целых чисел у значения 3 нет мультипликативной инверсии. Традиционная мультипликативная инверсия числа 3, которая равна '/3) лежит за пределами системы целых чисел. Но в системе целых чисел по модулю 7 у значения 3 есть мультипликативная инверсия, равная (как мы увидели) 5.

Когда же у значения х есть мультипликативная инверсия в системе по модулю ml Математики говорят, что если хит — два положительных целых числа, таких что х < т и х и т взаимно простые (это означает, что единственное целое, на которое без остатка делятся и х, и т, равно 1), то у значения х будет мульти-i пликативная инверсия в модульной системе по модулю т. Например, 6 меньше 13 и у этих двух значений единственный общий делитель равен 1. Поэтому у 6 должна быть мультипликативная инверсия в системе по модулю 13. Действительно, инверсией является число 11, так как 6 х 11 = 66, что при делении на 13 дает в остатке 1. Поэтому 6x11 = 1 (mod 13).

То, что у некоторых целых чисел есть мультипликативные инверсии в модульных системах, может с первого взгляда показаться странным. В частности, так как 6 и 11 — мультипликативные инверсии в системе по модулю 13, мы обнаружим, что 6х 11 у. х = х для любого значения х. Действительно, 6х11хх=(6хИ)хх = х

Обратно к шифрованию


Обратите внимание, что, если значение х неотрицательно и меньше, чем модуль т, то х (mod m) равно х. Это значит, что при выполнении арифметических операций, обычные результаты которых лежат в диапазоне от 0 до т - 1, в модульной системе мы получим те же результаты. Так, если взять очень большое значение модуля, то можно выполнять обычные арифметические вычисления, даже не зная, находимся ли мы в традиционной арифметической системе или в модульной системе. В частности, так как сумма всех значений в списке 1 4 6 12 25 51 105 210 421 850

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

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

a, аг а3 я4 а5 а6 а7 а8 а9 аю

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

Если мы умножим каждую запись исходного списка на х, то получим список

а.\Хагх агх atx аъх а6х а7х asx a9x а1Ох,

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

К b2 b3 bA b5 b6 b-, bs bg bi0,

где каждая запись эквивалентна по модулю п соответствующим записям в списке

а1ха2х а3х а4х а5х а6х а7х аъх адх а1Ох.

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

а^ха-рс аъх аАх аъх а6х а7х asx a9x а1Ох.

Предположим, что нам дано число, равное сумме 6, + b3 + b5, и необходимо выбрать из списка

6, b2 b3 b4 b5 b6 b7 bs b9 bi0

записи, которые в сумме дают это значение. Так как

b, + Ь3 + Ь5 = (а,дг+ а3х + a5-^)(niod m)

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

у(й, + Ь3 + Ь5) = у{ахх+ а3х + а5х) (mod от) = ух(а{ + а3 + а5) (mod m) = (а, + а3 + а5) (mod m).

Это означает, что если мы умножим сумму значений, выбранных из списка 6, b2 b3 bt b5 b6 b7 b& b9 bi0

на у, разделим произведение наши запишем остаток, то этот остаток будет равен сумме соответствующих записей исходного списка

at a2 a3 aA a5 a6 a-, as ag a10.

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

0 ранце, выбрав соответствующие записи из списка

6, Ь2 Ь3 64 b5 b6 b7 bs b9 bm.

Вкратце, чтобы выбрать из списка 6, b2 b3 bt b5 b6 b7 bs b9 bl0

значения, составляющие сумму s, нам необходимо только вычислить значение s х у (mod m), найти в списке

а, а2 а3 а4 а5 а6 а7 а8 а9 а10

записи, сумма которых равна этому значению, и затем выбрать соответствующие значения в списке

bi b2 b3 b4 b5 be b7 b8 b9 bi0

Рассмотрим пример на списке

1 4 6 12 25 51 105 210 421 850

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

642 257 1541 771 2184 388 391 782 2206 304

Предположим, что теперь перед нами встала задача выбора из этого списка значений, сумма которых равна 4507. Мы умножаем 4507 на 18, получаем значение 81 126, делим его на 2311 и записываем остаток, равный 241. Затем обнаруживаем, что в исходном списке сумму 241 дают значения 6, 25 и 210. Так как это третья, пятая и восьмая записи в соответствующем списке, делаем вывод, что третья, пятая и восьмая записи в списке

642 257 1541 771 2184 388 391 782 2206 304

дают в сумме 4507. Действительно, значения 1541, 2184 и 782 решают исходную задачу о ранце.

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



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


1   ...   70   71   72   73   74   75   76   77   78

Похожие:

Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconОсновы работы с Sharepoint в какое место веб-страницы разрешается вставить новую веб-часть (в браузере)?
В какое представление веб-страницы будут вноситься изменения, если выбрать команду Настроить эту страницу?
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВведение в физику и технологию элементной базы ЭВМ и компьютеров
Введение   8
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСодержание
Содержание размещают после титульного листа отчёта (как правило, на стр. 2). Слово «Содержание» рас­полагают посередине страницы...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСоздание веб-страницы в простом текстовом редакторе
Давайте создадим  веб-страницу. Для этого нужно напечатать ее исходный код в простом текстовом редакторе  блокнот
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЗагрузка uploading теория
После того как набор html страниц веб-сайта создан. Все они связаны между собой с помощью ссылок. Страницы наполнены контентом. Таким...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЛитература 153 Алфавитный указатель 155 Предисловие редактора русского издания Глубокоуважаемые коллеги! Содержа­ние этой книги значительно шире и глуб­же, нежели заявлено в ее названии. Я бы назвала ее «Лечение и реставрация молочных зубов»
Предисловие редактора русского издания 6 Введение 9 Предисловие 11 Благодарности 13
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 icon        Информатика  Системы счисления и  арифметические основы эвм  
Введение   
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЯндекс - поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости, картинки, статьи
Яндекс — поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости,...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница