![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм Евклида для вычисления наибольшего общего делителя
Вычисление обратных величин В арифметике действительных чисел нетрудно вычислить мультипликативную обратную величину а~1 для ненулевого а: a-1 = 1/a или a * a-1 =1 Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку
В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения 4 * x º 1(mod 7) эквивалентно нахождению таких значений х и k, что 4 * x º 7 * k +1 где х и k-целые числа. Общая формулировка этой задачи -нахождение такого целого числа х, что a * x(mod n) = 1 Можно также записать a-1 º x(mod n) Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5 * 3 = 15 º 1(mod 14). С другой стороны, число 2 не имеет обратной величины по модулю 14. Вообще сравнение a-1 º x(mod n) имеет единственное решение, если а и n - взаимно простые числа. Если числа а и n не являются взаимно простыми, тогда сравнение не имеет решения [45]. a-1 º x(mod n)] Сформулируем основные способы нахождения обратных величин. Пусть целое число а Î{0,1,2,..., n-1}. Если НОД(а, n)=1, то a * i (mod n) при 1 = 0,1,2,...,n-1 является перестановкой множества {0,1,2,...,n-1}. Например, если а=3 и n=7(НОД(3,7}=1), то 3 * i (mod 7) при i = 0,1,2,…,6 является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества (0,1,2,...,6). Это становится неверным, когда НОД(а, n)¹1. Например, если а=2 и n= 6, то Если НОД(а, n) = 1, тогда существует обратное число а-1, 0<а-1<n, такое, что a * a-1 º 1(mod n) Действительно, a * i(mod n) является перестановкой 0,1,..., n-1, поэтому существует i, такое, что a * i º 1(mod n). Как уже отмечалось, набор целых чисел от 0 до n-1 называют полным набором вычетов по модулю п. Это означает, что для любого целого числа а(а>0) его вычет r = a(mod n)-это некоторое целое число в интервале от 0 до n-1. Выделим из полного набора вычетов подмножество вычетов, взаимно простых с п. Такое подмножество называют приведенным набором вычетов. Пример. Пусть модуль n=11- простое число. Полный набор вычетов по модулю 11. (0,1,2,…,10)
При формировании приведенного набора вычетов из них удаляется только один элемент-0. Приведенный набор вычетов по модулю 11 имеет 11-1=10 элементов. Вообще приведенный набор вычетов по модулю простого числа n имеет n-1 элементов.
Пример. Пусть модуль n=10. Полный набор вычетов по модулю n =10 {0,1,2,3,4,5,6,7,8,9}. Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этогоприведенного набора были исключены элементы: 0 (1 элемент), кратные 2 (4 элемента), кратные 5 (1 элемент), т.е. всего шесть элементов. Вычитая их из 10, получаем 10-1-4-1=4. т.е. четыре элемента в приведенном наборе. 10. Асимметричные шифры. Свойства, принципы построения. Криптографическая система с открытым ключом (также асимметричное шифрование, асимметричные шифры) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME. Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций f(x), что по известному x довольно просто найти значение f(x), тогда как определение x из f(x) сложно в смысле теории. Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x), можно вычислить x. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему. Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции f (ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:
Вход в систему теперь выглядит так: Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.
|
||||||
Последнее изменение этой страницы: 2017-01-24; просмотров: 255; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.143.40 (0.006 с.) |