Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
• мультипликативности
(ab) {mod ri\ = (a {mod n}b {mod я}) {mod я};
• сохранения степени
ab {mod n) = {a {mod л})* {mod и}.
Данные свойства операций над вычетами позволяют либо сначала вычислять вычеты, а затем выполнять операцию, либо сначала выполнять операцию, а затем вычислять вычеты. Операция вычисления вычета является гомоморфным отображением кольца целых чисел в кольцо вычетов по модулю я.
Наибольшим общим делителем (НОД) целых чисел а и Ъ называется наибольшее целое число, на которое делятся без остатка а и Ъ. Например: НОД(56, 98) = 14 и НОД(150, 19) = 1.
Простым числом называется целое число, которое делится без остатка только на единицу и на себя. Например: 7, 13, 139.
Целые числа а и Ъ называются взаимно простыми, если выполняется условие НОД(«, Ъ) = 1.
Целое число у называется мультипликативно обратным целому числу х по модулю п, если выполняется условие ху {mod я} = 1. Мультипликативно обратное целое число существует только тогда, когда х и п — взаимно простые числа. Если целые числа аи пне являются взаимно простыми, то сравнение а1 = х {mod n} не имеет решения. Если из полного набора вычетов по модулю п выделить подмножество вычетов, взаимно простых с я, то получим приведенный набор вычетов. Например:
{О, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} — полный набор вычетов по
модулю 11. Приведенным набором вычетов будет то же подмно
жество целых чисел, за исключением нуля;
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} — полный набор вычетов по
модулю 10. Приведенным набором вычетов будет подмножество
целых чисел {1, 3, 7, 9}.
Очевидно, что если п является простым числом, то приведенный набор вычетов по модулю я всегда содержит (л - 1) элемент (все целые числа от единицы до п - 1).
Значением функции Эйлера ф(я) будет число элементов в приведенном наборе вычетов по модулю п. Если п — простое число, то ф(л) = я - 1 и ф(л2) = п(п - 1). Если п - pq (р и q — простые числа и р * q), то ф(я) = (р - \)(q - 1).
В соответствии с малой теоремой Ферма, если а — целое число, я — простое число и НОД (а, п) = 1, то
a"~l= I {mod я}.
Обобщением малой теоремы Ферма является теорема Эйлера: если целые числа а и я являются взаимно простыми (НОД(я, я) = 1), то
а»(я)= 1 {mod я}.
4.2. Основные понятия криптологии. Симметричные и асимметричные криптосистемы
Назовем открытым текстом (plaintext) информацию, содержание которой может быть понятно любому субъекту. Под шифрованием (см. подразд. 1.1) понимается процесс преобразования открытого текста в шифротекст (cipher text) или криптограмму с целью сделать его содержание непонятным для посторонних лиц:
С = Е*(Р),
где С — шифротекст; Е — функция шифрования; к — ключ шифрования (дополнительный параметр функции шифрования); Р — открытый текст.
Очевидно, что без введения ключа шифрования применение одной и той же функции шифрования к одному и тому же открытому тексту приводило бы всегда к получению одного и того же шифротекста. В этом случае защищенность шифротекста целиком и полностью определялась бы неизвестностью для посторонних функции шифрования, что практически невозможно обеспечить (особенно при современном уровне развития информационных технологий).
Под расшифрованием понимается процесс обратного преобразования шифротекста в открытый текст:
Р = D*.(C),
где D — функция расшифрования; к' — ключ расшифрования (дополнительный параметр функции расшифрования).
Совокупность реализуемых функциями Е и D алгоритмов, множества возможных ключей, множеств возможных открытых текстов и шифротекстов принято называть криптосистемой. Если при шифровании и расшифровании используются одни и те же ключи (к= к'), то такую криптосистему называют симметричной. Очевидно, что ключ шифрования (он же — ключ расшифрования) в этом случае должен быть секретным.
Если при шифровании и расшифровании используются различные ключи, то такую криптосистему называют асимметричной. В этом случае один из этих ключей должен оставаться секретным (secret key), а другой может быть открытым (public key). Поэтому асимметричные криптосистемы иногда называют криптосистемами с открытым ключом.
Науку о защите информации с помощью шифрования называют криптографией (криптография в переводе означает загадочное письмо или тайнопись). Криптография известна из глубокой древности, а одним из первых ее методов следует, по-видимому, считать создание письменности.
125