Почему простые числа так важны?
Только не пишите "матапушта RSA", меня интересует, почему используются именно они, а не другие числа.
|
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
Нормы пользования. Некоторые права на материалы сайта защищены по условиям лицензии CreativeCommons. Движок
openSpace 0.8.25a и дизайн сайта © 2006-2007 Vlad "SATtva" Miller.
|
||||||||||||||||||||||||||
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
Матапушта не Райвист, Шамир и Адлеман, а ещё Эйлер, Ферма, Галуа?
А о чём писать? Об алгебраической структуре, обладающей определёнными свойствами по модулю простого числа (DH) — группа, или полупростого числа — кольца и группы "по модулю фи" (RSA). Даже во всякой экзотике с решётками тоже простые числа.
Без простого числа элементарно не получить цикличность группы и конечность поля.
Когда нужны двоичные операции, то для GF(2n) определяют неприводимый полином — тоже простое число в полиномиальном виде.
Имелось в виду "не отвечайте "потому что они используются в RSA", ценность такого ответа равна нулю", что я и написал в вопросе.
Напиши об этом. Я с математикой, стоящей за такого рода криптографией, знаком поверхностно.
комментариев: 9796 документов: 488 редакций: 5664
Для понимания некоего стандартного набора криптоалгоритмов достаточного совсем небольшого числа базовых понятий из алгебры и теории чисел (всякие экспериментальные направления на экзотических алгебрах пока оставим в стороне). Естественно, сама по себе эта математика известна задолго до того, как её приспособили для криптографии.
Допустим, у нас есть простое число p = 11. У него есть весь ряд (1 ... p-1) мультипликативных инверсий (x · y = 1 mod p):
а если взять непростое число, то для некоторых членов таких инверсий не будет. Для числа 10 в ряду {1 ... 9} будет только четыре инверсии:
Т.е. хрен вам, а не мультипликативная группа по модулю непростого числа. Зато для всех простых чисел есть полноценные группы с инверсиями и единицами.
Другой пример: в группе по модулю простого числа всегда можно найти генератор, элемент группы, который при возведении в степень даёт все остальные элементы группы (цикличность).
21=2 mod 11; 22=4 mod 11; 23=8 mod 11; 24=5 mod 11,
а если в виде таблицы:
Т.е., при возведении некоего генератора в степень по модулю простого числа p получили перестановку всех элементов от 1 до p-1. И это опять же справедливо для каждого простого p.
Более сложные структуры с обратимыми преобразованиями также строятся на основе простых чисел. Отсюда уже выводятся и RSA и DH, и некоторые преобразования в симм. алгоритмах (некоторые S-блоки, MDS-матрицы).
Поле картофельное видел? Понимаешь, что оно конечно? Хотя если в деревне не вырос, то да, это непоправимо.
[offtop]
Хотя конечное поле — уникальный объект. Все такие конечные поля изоморфны полю вычетов по модулю простых чисел. И эта специфика полей юзается.
[/offtop]
Это такой петросянистый юмор? Или академический снобизм?
На твоем картофельном поле есть мультипликативно обратный элемент?
А где доказательство существования генератора и как его находят? Опять же, почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?
Есть. Колорадский жук называется.
Борзый мьсе любезно просит unknownа своими славами начать пересказывать учебник по теории групп? Это такой толстый троллинг? Для самых ленивых есть ещё википедия.
Исходя из общих соображений — чтобы набор не убывал, а только переупорядочивался. Алгебраически такая перестановка ещё и обратима, потому с ней проще работать.
комментариев: 9796 документов: 488 редакций: 5664
Есть похожие направления, хотя не столь радикально сформулированные.
К концу одной новости упоминается система MQQ.
В этом одна из засад. В том, что напрямую эффективно ничего не посчитать, а когда пытаются сгенерировать такую абстрактную структуру, то делают это с помощью традиционных способов. Получается, что с помощью обычной группы генерируется более абстрактная группа и производятся некие прямые и обратные преобразования. Выигрыш в стойкости и скорости получается неочевидным (хотя теоретически возможен за счёт оптимизаций, что и привлекает исследователей), сложность системы при этом растёт вместе со всеми доказательствами. Хотя, перенос DH в группы эллиптических кривых — очевидный успех такого подхода.
Там где нужно поле. Хотя в RSA используется кольцо с экспоненциальными инверсиями, но порядок "фи" (p – 1)(q – 1) и здесь вылезает неслучайно. Также как ключ шифрования и расшифрования (ну прямо внезапно, да?) являются обратными множителями (мультипликативными инверсиями) по модулю фи. Т.е. не "простые числа, потому что RSA", а "RSA, DH и ещё куча всего невозможно без простых чисел".
В следствиях из теорем Лагранжа и Эйлера.
Простого алгоритма нет. Есть эвристики и проверки.
Не всегда важно. Важно знать порядок (цикличности) получаемой подгруппы.
В DH можно (нужно) использовать генератор не всей группы (примитивный или первообразующий корень), а сильной подгруппы. Так и считать быстрее и стойкость сохраняется. При этом структура подгруппы будет определена свойствами простых чисел. Например, для сильного простого числа p=2q + 1 будет только четыре подгруппы. Тогда можно работать с заведомо сильной подгруппой порядка q. В реальности выбор подгрупп в DH ещё более заоптимизирован. Т.е. можно допустить, чтобы набор убывал, но надо точно заранее показать по порядку подгруппы, насколько он будет убывать. Чтобы не получить слабую подгруппу с малой цикличностью, защититься от атак навязывания слабых подгрупп, утечки информации о логарифме через вычисления по символу Лежандра.
Иногда бывает нужна цикличность всей группы. Как справедливо отмечено, это нужно там, где требуется обратимость.
А кому он обратен? Твоей маме?
Если дадите понятный и не слишком заучный учебник – буду благодарен. unknown, не то чтобы это была критика, но те, кто могут понять твой пост, вопросов задавать не будут.
Слово "троллинг" каждый определяет для себя, да?
Не поверишь – я там был.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 1515 документов: 44 редакций: 5786
Напомнило:
xxx: К нам в общагу проникли какие-то гопы, поднялись на второй этаж, напоролись на тебя и спросили: "А тут девушки нормальные есть?" На что ты ответил: "А нормальные – это какие? Которые со своим сопряженным коммутируют?" Они профигели и тихо ответили: "Ну, как это, ну, в общем, да".
я: В упор не помню! Но вопрос "А тут девушки нормальные есть?" с большим трудом припоминается.
xxx: Ну вот я запомнил, потому что ржал над этим оооооооооооочень долго. Девушкам рассказывай — пусть понимают, что такое быть нормальной!
*Cокомнатник по общежитию, мой третий курс.