Помощь студентам в учебе
ПАРАМЕТРИЗОВАННЫЕ РЕШЕТКИ И ЧАСТИЧНЫЕ ЗАТЕМНЕННЫЕ ЦИФРОВЫЕ ПОДПИСИ
|
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
Глава 1. Системы проверки подлинности сообщения. Общие сведения
о подписях и их усовершенствованных аналогах . . . . . . . . . . . . . . 8
§ 1. Техническая концепция систем аутентификации . . . . . . . . . 8
§ 1.1. Симметричные системы аутентификации . . . . . . . . . . . . . . .8
§ 1.2. Асимметричные системы аутентификации . . . . . . . . . . . . . .9
§ 2. Требования к цифровой подписи . . . . . . . . . . . . . . . . . . . . . . . . 11
§ 3. Применение цифровой подписи в ЭДО . . . . . . . . . . . . . . . . . . 13
§ 4. Метод шифрования RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
§ 5. Затемненные цифровые подписи . . . . . . . . . . . . . . . . . . . . . . . . 17
Глава 2. Частично затемненные подписи . . . . . . . . . . . . . . . . . . . . . . . . 20
§ 1. Особенности частично затемненных подписей. . . . . . . . . . . 20
§ 2. Частично затемненная подпись на основе RSA . . . . . . . . . .21
§ 3. Частично затемненная подпись на основе задачи дискретного логарифмирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Глава 3. Постквантовая криптография . . . . . . . . . . . . . . . . . . . . . . . . . . 24
§ 1. Основы теории решёток. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
§ 2. Сложные задачи на решётках . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
§ 3. Решётки в теории криптографии. . . . . . . . . . . . . . . . . . . . . . . . 25
§ 4. LLL-алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Глава 4. Кольца целых алгебраических чисел . . . . . . . . . . . . . . . . . . . 30
§ 1. Поля алгебраических чисел и кольца целых алгебраических
чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
§ 2. Круговые поля. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Глава 5. Новый пример частично затемненной подписи, основанной
на решётках. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
§ 1. Идея цифровых подписей на решётках. . . . . . . . . . . . . . . . . . 33
2§ 2. Модели решёток над полем Q . . . . . . . . . . . . . . . . . . . . . . . . . . .33
§ 3. Доказательство основной теоремы. . . . . . . . . . . . . . . . . . . . . . . 34
§ 4. О выборе решёток. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
§ 5. Основная идея протокола подписи. . . . . . . . . . . . . . . . . . . . . . . 38
Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Глава 1. Системы проверки подлинности сообщения. Общие сведения
о подписях и их усовершенствованных аналогах . . . . . . . . . . . . . . 8
§ 1. Техническая концепция систем аутентификации . . . . . . . . . 8
§ 1.1. Симметричные системы аутентификации . . . . . . . . . . . . . . .8
§ 1.2. Асимметричные системы аутентификации . . . . . . . . . . . . . .9
§ 2. Требования к цифровой подписи . . . . . . . . . . . . . . . . . . . . . . . . 11
§ 3. Применение цифровой подписи в ЭДО . . . . . . . . . . . . . . . . . . 13
§ 4. Метод шифрования RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
§ 5. Затемненные цифровые подписи . . . . . . . . . . . . . . . . . . . . . . . . 17
Глава 2. Частично затемненные подписи . . . . . . . . . . . . . . . . . . . . . . . . 20
§ 1. Особенности частично затемненных подписей. . . . . . . . . . . 20
§ 2. Частично затемненная подпись на основе RSA . . . . . . . . . .21
§ 3. Частично затемненная подпись на основе задачи дискретного логарифмирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Глава 3. Постквантовая криптография . . . . . . . . . . . . . . . . . . . . . . . . . . 24
§ 1. Основы теории решёток. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
§ 2. Сложные задачи на решётках . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
§ 3. Решётки в теории криптографии. . . . . . . . . . . . . . . . . . . . . . . . 25
§ 4. LLL-алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Глава 4. Кольца целых алгебраических чисел . . . . . . . . . . . . . . . . . . . 30
§ 1. Поля алгебраических чисел и кольца целых алгебраических
чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
§ 2. Круговые поля. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Глава 5. Новый пример частично затемненной подписи, основанной
на решётках. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
§ 1. Идея цифровых подписей на решётках. . . . . . . . . . . . . . . . . . 33
2§ 2. Модели решёток над полем Q . . . . . . . . . . . . . . . . . . . . . . . . . . .33
§ 3. Доказательство основной теоремы. . . . . . . . . . . . . . . . . . . . . . . 34
§ 4. О выборе решёток. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
§ 5. Основная идея протокола подписи. . . . . . . . . . . . . . . . . . . . . . . 38
Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
С самого возникновения теории криптографии, она начала стремительно развиваться. Примерно в 1970-ом году зарождается математическая
криптография. С этого времени началась изучаться криптостойкость появлявшихся методов шифрования. Современна криптография насчитывает
40 летний период развития. Существенная новизна заключалась в появлении нового ключа: открытого.
Появление усовершенствованных средств вычисления, развитие их производительности — главный фактор эволюционирования такого важного и
основополагающего гаранта безопасного обмена информациями — криптографии.
Уровень защищенности систем шифрования со временем ухудшается:
некогда криптостойкие симметричные системы шифрования становились
небезопасными. На их замену пришли симметричные. Стороны, осуществлявшие обмен информациями, не передавали ключи. Сейчас же, чтобы
получить доступ к зашифрованным данным, необходимо решить задачу
факторизации больших простых чисел. Также, решение задачи дискретного логарифмирования разрушит защищенность одного из методов шифрования.
В наш новый XXI век наступил этап квантовый этап развития криптографии. Мир на пороге изобретения совершенно новой вычислительной машины: квантового компьютера. В связи с этим, существует острая
необходимость обновления существующих, пока еще безопасных, методов
шифрования. Наступит день, когда изобретут квантовый компьютер. Злоумышленники получат мощнейший аппарат для управления всеми электронными вариантами обмена информациями. Необходимо отметить, что
электронные платежи окажутся небезопасными.
4Криптография требует постоянного эволюционирования. В современной криптографии используются решетки, кольца и их идеалы. Как выяснилось, при некоторых условиях, они тесно взаимосвязаны. В теории
решеток есть несколько сложнейших задач, неподвластных квантовому
компьютеру, что явилось фундаментальной теорией постквантовой криптографии.
В нашей работе изучаются частично затемненные цифровые подписи
(partially blind signatures). Строятся новые примеры таких подписей. В
частности, конструируется новый класс частично затемненных подписей,
основанных на сложности задач на решетках.
Подписи такого типа могут иметь в перспективе важное значение, потому что по состоянию дел на данный момент, их невозможно подделать с
помощью квантового компьютера, так как квантовый компьютер не обладает способностью решать сложные задачи на решетках быстрее обычного.
Частично затемненные цифровые подписи используются в финансовой
криптографии (электронные деньги) и в системах электронного голосования. Обзор исследований в этом направлении можно найти в статье [4].
Опишем вкратце содержание нашей работы.
В главе I напоминаются основные определения и факты о цифровых
подписях, а также затемненных цифровых подписях. В качестве источников информации явились книги [14], [10], [11], а так же [4].
В главе II описываются частично затемненные подписи. Приведены Новые примеры таких подписей, являющихся модификациями подписи RSA.
Эти примеры были ранее опубликованы в [8], [9], [6].
В главе III мы начинаем излагать подготовительный материал к основному результату из главы V. Глава посвящена решёткам их применениям
в криптографии.
В x1 приводятся основные определения, способы задания решёток, и
5формируются основные вычислительно сложные задачи на решетках - задача нахождения кратчайшего вектора решётки, и задача нахождения вектора решетки, ближайшего к данному. Источники информации: глава VII
книги [17], а также статья [20].
В x2 освещается LLL-алгоритм. Тут мы следуем книге [3] и др.
В x3 описывается, как эта техника применяется для конструирования
(обычных) цифровых подписей.
В главе IV описывается класс решёток, с помощью которых будет сконструирована подпись из главы V. Эти решётки возникают в теории алгебраических чисел [2], [1], [5], [13]. Напоминаются определения полей алгебраических чисел и идеалов в таких кольцах. Поля алгебраических чисел
являются конечномерными векторными пространствами над полем рациональных чисел Q, а кольца целых алгебраических чисел и их идеалы
— решётки в этих пространствах. Особую роль в нашей работе будут играть поля деления круга (циклотомические поля). Они достаточно просто
устроены и хорошо изучены, а их группы автоморфизмов (группы Галуа)
являются циклотомическими и легко описываются.
Наконец, в последней, V главе излагается принципиальная схема нового
протокола частично затемненной подписи, основанной на решётках того
типа, который описан в главе IV. Эта подпись в целом основана на тех же
идеях, которые изложены в x3 главы III, но имеет следующие характерные
особенности:
1) используемые решётки — идеалы в кольце целых алгебраических чисел, которые соответствуют некоторому полю алгебраических чисел,
которое получается модификацией циклотомического поля.
2) параметр (натуральное число), который необходим для построения
частично затемненной подписи, вводится прямо в определения поля
6и идеала.
3) средством затемнения идентификатора (номера) электронной банкноты служит случайно выбранный автоморфизм поля. Эти особенности заметно отличают нашу подпись от единственного пока известного примера частично затемненной подписи, основанной на решётках
[23].
Основные результаты работы опубликованы в [8], [9], [6], [7] и доложены на молодежных школах-конференциях "Лобачевские чтения"в 2017 и
2018 годах, а также на студенческих научных конфренциях ИММ КФУ, в
частности на последней, 27 апреля 2019 года.
криптография. С этого времени началась изучаться криптостойкость появлявшихся методов шифрования. Современна криптография насчитывает
40 летний период развития. Существенная новизна заключалась в появлении нового ключа: открытого.
Появление усовершенствованных средств вычисления, развитие их производительности — главный фактор эволюционирования такого важного и
основополагающего гаранта безопасного обмена информациями — криптографии.
Уровень защищенности систем шифрования со временем ухудшается:
некогда криптостойкие симметричные системы шифрования становились
небезопасными. На их замену пришли симметричные. Стороны, осуществлявшие обмен информациями, не передавали ключи. Сейчас же, чтобы
получить доступ к зашифрованным данным, необходимо решить задачу
факторизации больших простых чисел. Также, решение задачи дискретного логарифмирования разрушит защищенность одного из методов шифрования.
В наш новый XXI век наступил этап квантовый этап развития криптографии. Мир на пороге изобретения совершенно новой вычислительной машины: квантового компьютера. В связи с этим, существует острая
необходимость обновления существующих, пока еще безопасных, методов
шифрования. Наступит день, когда изобретут квантовый компьютер. Злоумышленники получат мощнейший аппарат для управления всеми электронными вариантами обмена информациями. Необходимо отметить, что
электронные платежи окажутся небезопасными.
4Криптография требует постоянного эволюционирования. В современной криптографии используются решетки, кольца и их идеалы. Как выяснилось, при некоторых условиях, они тесно взаимосвязаны. В теории
решеток есть несколько сложнейших задач, неподвластных квантовому
компьютеру, что явилось фундаментальной теорией постквантовой криптографии.
В нашей работе изучаются частично затемненные цифровые подписи
(partially blind signatures). Строятся новые примеры таких подписей. В
частности, конструируется новый класс частично затемненных подписей,
основанных на сложности задач на решетках.
Подписи такого типа могут иметь в перспективе важное значение, потому что по состоянию дел на данный момент, их невозможно подделать с
помощью квантового компьютера, так как квантовый компьютер не обладает способностью решать сложные задачи на решетках быстрее обычного.
Частично затемненные цифровые подписи используются в финансовой
криптографии (электронные деньги) и в системах электронного голосования. Обзор исследований в этом направлении можно найти в статье [4].
Опишем вкратце содержание нашей работы.
В главе I напоминаются основные определения и факты о цифровых
подписях, а также затемненных цифровых подписях. В качестве источников информации явились книги [14], [10], [11], а так же [4].
В главе II описываются частично затемненные подписи. Приведены Новые примеры таких подписей, являющихся модификациями подписи RSA.
Эти примеры были ранее опубликованы в [8], [9], [6].
В главе III мы начинаем излагать подготовительный материал к основному результату из главы V. Глава посвящена решёткам их применениям
в криптографии.
В x1 приводятся основные определения, способы задания решёток, и
5формируются основные вычислительно сложные задачи на решетках - задача нахождения кратчайшего вектора решётки, и задача нахождения вектора решетки, ближайшего к данному. Источники информации: глава VII
книги [17], а также статья [20].
В x2 освещается LLL-алгоритм. Тут мы следуем книге [3] и др.
В x3 описывается, как эта техника применяется для конструирования
(обычных) цифровых подписей.
В главе IV описывается класс решёток, с помощью которых будет сконструирована подпись из главы V. Эти решётки возникают в теории алгебраических чисел [2], [1], [5], [13]. Напоминаются определения полей алгебраических чисел и идеалов в таких кольцах. Поля алгебраических чисел
являются конечномерными векторными пространствами над полем рациональных чисел Q, а кольца целых алгебраических чисел и их идеалы
— решётки в этих пространствах. Особую роль в нашей работе будут играть поля деления круга (циклотомические поля). Они достаточно просто
устроены и хорошо изучены, а их группы автоморфизмов (группы Галуа)
являются циклотомическими и легко описываются.
Наконец, в последней, V главе излагается принципиальная схема нового
протокола частично затемненной подписи, основанной на решётках того
типа, который описан в главе IV. Эта подпись в целом основана на тех же
идеях, которые изложены в x3 главы III, но имеет следующие характерные
особенности:
1) используемые решётки — идеалы в кольце целых алгебраических чисел, которые соответствуют некоторому полю алгебраических чисел,
которое получается модификацией циклотомического поля.
2) параметр (натуральное число), который необходим для построения
частично затемненной подписи, вводится прямо в определения поля
6и идеала.
3) средством затемнения идентификатора (номера) электронной банкноты служит случайно выбранный автоморфизм поля. Эти особенности заметно отличают нашу подпись от единственного пока известного примера частично затемненной подписи, основанной на решётках
[23].
Основные результаты работы опубликованы в [8], [9], [6], [7] и доложены на молодежных школах-конференциях "Лобачевские чтения"в 2017 и
2018 годах, а также на студенческих научных конфренциях ИММ КФУ, в
частности на последней, 27 апреля 2019 года.
Результат работы — новая частично затемненная подпись на основе
решёток. На данный момент известна единственная подобная подпись. В
нашей работе общая идея с этой подписью, однако есть существенные отличия. В протоколе взаимодействуют три участника. И в нашем случае,
применяется известная только Банку решётка.
В первой главе я обратился к истокам криптографии, подробно ознакомился с системами аутентификации. Представил требования к цифровым
подписям, а также осветил метод шифрования RSA. В последнем параграфе первой главы шла речь о затемненных цифровых подписях. Эти сведения были использованы в последующих главах. Так как работа дальше
велась именно с затемненными вариантами существующих методов шифрования.
Во второй главе рассматривались частично затемненные подпись, это
так называемые подписи с параметром или же с дополнительной информацией. Приведен пример частично затемненной подписи на основе RSA и
подписи, основанной на проблеме дискретного логарифмирования.
Работа продолжается главой о постквантовой криптографии, в которой рассматривалась основы теории решёток, сложные задачи и алгоритм,
для нахождения редуцированного базиса. Необходимо отметить, в процессе исследования вышеуказанных тем, нашлась статья, которая вдохновила
на дальнейшие исследования.
решёток. На данный момент известна единственная подобная подпись. В
нашей работе общая идея с этой подписью, однако есть существенные отличия. В протоколе взаимодействуют три участника. И в нашем случае,
применяется известная только Банку решётка.
В первой главе я обратился к истокам криптографии, подробно ознакомился с системами аутентификации. Представил требования к цифровым
подписям, а также осветил метод шифрования RSA. В последнем параграфе первой главы шла речь о затемненных цифровых подписях. Эти сведения были использованы в последующих главах. Так как работа дальше
велась именно с затемненными вариантами существующих методов шифрования.
Во второй главе рассматривались частично затемненные подпись, это
так называемые подписи с параметром или же с дополнительной информацией. Приведен пример частично затемненной подписи на основе RSA и
подписи, основанной на проблеме дискретного логарифмирования.
Работа продолжается главой о постквантовой криптографии, в которой рассматривалась основы теории решёток, сложные задачи и алгоритм,
для нахождения редуцированного базиса. Необходимо отметить, в процессе исследования вышеуказанных тем, нашлась статья, которая вдохновила
на дальнейшие исследования.