Криптографическая система на основе канонических систем счисления

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

КРИПТОГРАФИЧЕСКАЯ СИСТЕМА НА ОСНОВЕ КАНОНИЧЕСКИХ СИСТЕМ СЧИСЛЕНИЯ
Федосеев В. А.
Самарский государственный аэрокосмический университет
В статье рассматривается криптографическая система, базирующаяся на существования позиционных систем счисления в квадратичных полях.
Введение
В работах [1, 2] введено понятие канонических систем счисления (КСС) в кольцах целых элементов квадратичных полей, позволяющих представлять элементы таких колец конечными линейными комбинациями степеней некоторого целого элемента квадратичного поля по аналогии с обычными позиционными системами счисления для целых чисел. В данной работе рассматривается приложение этой относительно новой теории к задачам криптографии.
Сформулируем основные определения и необходимые сведения из теории КСС.
Пусть Q ((d) — квадратичное поле:
Q (d) = {z = a + b4d: a, b eQ},
z = a + b4d = Rat (z) + 4dIrr (z), где d есть свободное от квадратов целое число.
Пусть S (d) есть кольцо его целых элементов:
S ((d) = {z e Q ((d): Norm (z) = a2 — db2, Tr (z) e z}
Определение 1. Целое алгебраическое число, а = A + *Jd есть основание канонической системы
счисления в кольце S (d) целых элементов поля
Q ((d) если любой элемент z eS (d) представляется единственным образом конечной суммой
k (z)
z = Z zj а1 ,
j=о
где «цифры» zj принадлежат конечному подмножеству
N ={0,1,… ,| Norm (а) -1}, Norm (а) = A2 — d.
В зависимости от того, является ли поле Q (-Jd)
вещественным (d & gt- 0) или мнимым (d & lt- 0), исчерпывающее описание канонических систем счисления дано в [1, 2]. Нам потребуется частный случай существования КСС, который мы сформулируем в форме леммы.
Лемма 1. (а) Пусть поле Q (d) — вещественное, 0 & lt- d = 2,3 (mod 4). Тогда алгебраическое число, а = A ± Vd является основанием канонической
системы счисления в кольце S ((d) = Z ((d) тогда и только тогда, когда A e Z и 0 & lt- -2A & lt- A2 — d & gt- 2.
(b) Пусть поле Q ((d) — вещественное, 0 & lt- d = 1(mod4). Тогда алгебраическое число
а = 2(в±[d) является основанием канонической
системы счисления в кольце S ((d)з Z ((d) тогда и только тогда, когда B e Z нечетно и
0 & lt--в & lt- -4 (в2 — d)& gt- 2
Существует рекуррентная процедура, позволяющая находить «цифры» zt для представления целого элемента квадратичного поля в КСС [3]
Лемма 2. Пусть целое d & gt- 2 свободно от квадратов.
(а) Пусть d = 2,3(mod4), то, а = A±*Jn — базис канонической системы счисления,
z = x + y4d e S (4d), N (а) = Norm^) = A2 — d.
Определим последовательность st рекуррентным соотношением:
S-1 (z) = +yN (а) ,
s0 (z) = x + Ay ,
Jk+1
(z) = 2 A
sk (z) sk-1 (z)
N (а) N (а)
, k & gt- 0.
(b) Пусть d = 1(mod4), а= - (в±Vd) — базис
канонической
1 + 4d
z = x ±
системы
счисления,
-У'-
: S ((d). Определим последова-
тельность si рекуррентным соотношением:
S-1 (z) = +yN (а)
i -B-1
s0 (z) = x+ -T& quot- У
2
+1
(z) = A
sk (z) sk-1 (z)
N (а) N (а)
к & gt- 0.
Тогда
z = Z zkак, где zk = sk (z)(modN (а)).
к & gt-0
Описание криптосистемы
Пусть шифротекст имеет числовой эквивалент -целое число г = г + 0-л/й. Секретными ключами криптосистемы являются целые числа А, й, такие,
что целое квадратичное число, а = А + л[й или
1 (А ±у/й) (в
а = -
(в зависимости от вычета числа
й (mod4)) является основанием канонической 2'- -
значной КСС ('- - открытый ключ).
Если Алиса хочет послать сообщение г = г + 0 — [й Бобу, то она вычисляет в соответствии с Леммой 2 последовательность цифр г}- для представления г в КСС с основанием а. Так как каждая из цифр г^ однозначно представляется '- -битовым
вектором, то сообщение г преобразуется в шифро-текст — битовую последовательность длины '-К, где К — число цифр представления сообщения г в КСС с основанием, а.
Получив сообщение, Боб выделяет из битовой последовательности '- -членные блоки — обычные двоичные коды «цифр» г}- и, зная основание а,
восстанавливает сообщение.
Параметры криптосистемы
При изучении криптографической системы одним из основных вопросов является выбор таких параметров, А и Ы, при которых задача шифрования текста была бы как можно более простой, а дешифрации — как можно более сложной.
Изучим взаимосвязь параметров и ограничения, определяющие их выбор. Число N должно быть свободно от квадратов и N = 2,3 (п4). Число, А & lt- 0
и |А| & lt- 2'--1. Также эти два параметра связаны соотношением А2 — N = 2'-.
Таким образом, перед отправителем фактически ставится задача генерации числа, А, удовлетворяющего следующим соотношениям:
А & lt- 0, (1)
21−2А & lt- 2'--1, А2 — 2'- = 3 (п^ 4)
(2) (3)
и свободно от квадратов.
Такое число однозначно определяет криптосистему. При достаточно большой степени '- найдется большое количество чисел, удовлетворяющих этим соотношениям, и раскрытие ключа (А, Ы) представляется достаточно тяжелой задачей.
Таким образом, основная задача, стоящая перед разработчиком криптосистемы, заключается в проверке большого целого числа на отсутствие квадратичных сомножителей в его каноническом разложении на простые сомножители. Это может быть сделано различными методами.
Рассмотрим отдельно случай, когда выбранное открытое число '- является четным: '- = 2к. Тогда
N = А2 — 22к =(А — 2к)(А + 2к). Число N свободно от квадратов тогда и только тогда, когда числа, А — 2к и, А + 2к свободны от квадратов и взаимно просты. Взаимная простота быстро проверяется по алгоритму Евклида, а проверка на взаимную простоту этих чисел осуществляется быстрее, чем для числа N.
В отличие от разработчика, выбирающего параметры криптосистемы, взломщик вынужден проверять большое количество чисел, подчиняющихся условиям (1) — (3). В том числе и проверять на наличие квадратичных сомножителей. Априорная информация, следующая из условия (3) не облегчает задачу раскрытия ключа, которая сводится, в частности, к «трудной» вычислительной задаче факторизации целых чисел.
Устойчивость шифротекста к декодированию методом частотного анализа Рассмотрим простейший способ приведения открытого текста к виду г = х + е 8 ([й): текст
переводится кодом подстановки, в котором каждой букве соответствует ее номер в алфавите (от 0 до 31, без буквы «ё», пробелов и знаков препинания), в число г1, а число г2 принимается равным нулю. Таким образом, в числе г = г1 каждые 5 бит соответствуют одной букве алфавита. Если в шифротексте удастся выделить битовые куски, соответствующие отдельным буквам, то взломщик при помощи частотного анализа сможет дешифровать текст. Наша задача — изучить связь последовательности битов числа г с последовательностью битов шифротекста.
В первую очередь заметим, что число бит открытого текста равно числу букв, помноженному на 5, т. е. пропорционально длине сообщения, тогда как число бит шифротекста & lt-'- ('- +1), то есть, ограничено параметром кодирования, и, следовательно, не пропорционально длине сообщения. Это значит, что между последовательностями битов не существует точного соответствия. Однако определенные связи между ними все же имеют место.
Пример 1. Пусть открытый текст — & quot-ООО"-, в битовой форме 11 100 111 001 110. Шифротекст при кодировании с параметрами, А = -7 и '- = 5:
100 101 001 010 010 094 577 910 131 571 158 513 876 992
10
Шифротекст при кодировании с параметрами, А = -37 и '- = 10:
1 000 001 111 001 111 038 953 518 719 303 680 Как видим, в обоих случаях несколько младших бит совпали с открытым текстом. Однако, и в первом, и во втором случае остаются еще большие несовпадающие битовые участки, длина которых значительно превышает длину одной буквы (что подтверждает сказанное выше о длине шиф-ротекста).
Пример 2. Пусть открытый текст — слово «КАПКАН»:
10 100 000 001 111 011 196 753 936 384 Шифротекст при кодировании с параметрами A = -7 и t = 5:
100 101 011 011 001 107 250 696 511 931 478 089 662 464 1 001 011 110 101 100 985 024 768 007 028 604 928 1 000 000 000 001 101
Шифротекст при кодировании с параметрами A = -37 и t = 10:
111 111 111 001 110 012 272 237 747 495 773 229 023 232 1 001 001 101 001 100 058 917 446 828 949 504
При кодировании этого слова также совпали несколько младших бит шифра и текста, причем их количество практически не изменилось от увеличения слова. Изменяется оно при увеличении параметров кодирования (возрастает). Это явление объясняется тем, что эти биты относятся к свободному члену в канонической системе счисления, и значит равны битам исходного числа. В остальной же части шифротекста невозможно выделить отдельные буквы, следовательно, взломщик не может применить частотный анализ для
декодирования текста. При большом размере шифруемого текста известность для взломщика нескольких последних букв без возможности выделения остальных не является угрожающим фактором. К тому же эти последние буквы могут не нести информацию (например, заполнение конца текста многоточиями).
Благодарности
Работа выполнена при поддержке российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE).
Литература
1. Katai I., Kovacs B. Kanonische Zahlensysteme in der Theorie der quadratischen Zahlen // Acta Sci. Math. (Szeged) 42, 1980, pp. 99−107.
2. Katai I., Kovacs B. Canonical Number Systems in Imaginary Quadratic Fields // Acta Math. Acad. Sci. Hungari-cae, v. 37, 1981, pp. 159−164.
3. Thuswardner J.M. Elementary properties of canonical number systems in quadratic fields // Applications of Fibonacci Numbers, F.T. Howard (Editor), v. 7, Kluwer, 1998, pp. 405−409.

ПоказатьСвернуть
Заполнить форму текущей работой