Только не пишите "матапушта RSA", меня интересует, почему используются именно они, а не другие числа.
Комментарии
— Гость (12/12/2011 11:44) Где важны? В криптографии? Ну потому что вычислительно трудная задача — это именно факторизация большого числа, являющегося произведением двух больших простых чисел. Всё остальное факторизуется легко.
— SATtva (12/12/2011 11:50) Сами простые числа имеют при этом достаточно случайное распределение.
Матапушта не Райвист, Шамир и Адлеман, а ещё Эйлер, Ферма, Галуа?
А о чём писать? Об алгебраической структуре, обладающей определёнными свойствами по модулю простого числа (DH) — группа, или полупростого числа — кольца и группы "по модулю фи" (RSA). Даже во всякой экзотике с решётками тоже простые числа.
Без простого числа элементарно не получить цикличность группы и конечность поля.
Когда нужны двоичные операции, то для GF(2n) определяют неприводимый полином — тоже простое число в полиномиальном виде.
— Гость (12/12/2011 15:18) Потому что другие числа представимы в виде произведения простых. А вообще вопрос сродни "почему здания строят из кирпечей". Ну технология такая!
— Гость (13/12/2011 15:25) Почему диффи-хеллман должен быть по простому модулю?
>Только не пишите "матапушта RSA"
Имелось в виду "не отвечайте "потому что они используются в RSA", ценность такого ответа равна нулю", что я и написал в вопросе.
>А о чём писать? Об алгебраической структуре, обладающей определёнными свойствами по модулю простого числа (DH) — группа, или полупростого числа — кольца и группы "по модулю фи" (RSA). Даже во всякой экзотике с решётками тоже простые числа.
>Без простого числа элементарно не получить цикличность группы и конечность поля.
Напиши об этом. Я с математикой, стоящей за такого рода криптографией, знаком поверхностно.
Для понимания некоего стандартного набора криптоалгоритмов достаточного совсем небольшого числа базовых понятий из алгебры и теории чисел (всякие экспериментальные направления на экзотических алгебрах пока оставим в стороне). Естественно, сама по себе эта математика известна задолго до того, как её приспособили для криптографии.
Допустим, у нас есть простое число p = 11. У него есть весь ряд (1 ... p-1) мультипликативных инверсий (x · y = 1 mod p):
1
2
3
4
5
6
7
8
9
10
1
6
4
3
9
2
8
7
5
10
а если взять непростое число, то для некоторых членов таких инверсий не будет. Для числа 10 в ряду {1 ... 9} будет только четыре инверсии:
1
2
3
4
5
6
7
8
9
1
-
7
-
-
-
3
-
9
Т.е. хрен вам, а не мультипликативная группа по модулю непростого числа. Зато для всех простых чисел есть полноценные группы с инверсиями и единицами.
Другой пример: в группе по модулю простого числа всегда можно найти генератор, элемент группы, который при возведении в степень даёт все остальные элементы группы (цикличность).
21=2 mod 11; 22=4 mod 11; 23=8 mod 11; 24=5 mod 11,
а если в виде таблицы:
1
2
3
4
5
6
7
8
9
10
2
4
8
5
10
9
7
3
6
1
Т.е., при возведении некоего генератора в степень по модулю простого числа p получили перестановку всех элементов от 1 до p-1. И это опять же справедливо для каждого простого p.
Более сложные структуры с обратимыми преобразованиями также строятся на основе простых чисел. Отсюда уже выводятся и RSA и DH, и некоторые преобразования в симм. алгоритмах (некоторые S-блоки, MDS-матрицы).
— Гость (14/12/2011 00:17) Если так важно, что множество образует группу, не проще ли отказаться от чисел как от одного из её представлений и рассматривать криптографию как некую подобласть абстрактной алгебры? Когда надо будет "заземлить" криптографию в практическую область, после всех доказательств, можно придумать как оптимальней представлять элементы групп (ну или там других алгебраических структур) числами. Более того, произведение таких элементов группы можно определить через "абстрактные стрелки" — оно даже не обязано соответствовать какой-то реальной арифметике, важно лишь чтобы выполнялись замкнутость по операции умножения, ассоциативность, существование обратного и единицы.
— Гость (14/12/2011 00:26)
>>Без простого числа элементарно не получить цикличность группы и конечность поля.
>Напиши об этом. Я с математикой, стоящей за такого рода криптографией, знаком поверхностно.
Поле картофельное видел? Понимаешь, что оно конечно? Хотя если в деревне не вырос, то да, это непоправимо.
[offtop] Хотя конечное поле — уникальный объект. Все такие конечные поля изоморфны полю вычетов по модулю простых чисел. И эта специфика полей юзается.
[/offtop]
— Гость (14/12/2011 04:23)
>Поле картофельное видел? Понимаешь, что оно конечно? Хотя если в деревне не вырос, то да, это непоправимо.
Это такой петросянистый юмор? Или академический снобизм?
На твоем картофельном поле есть мультипликативно обратный элемент?
— Гость (14/12/2011 04:29) Для группы по модулю N мультипликативно обратные элементы будут для всех взаимно простых с N чисел. А где это так важно, чтобы любое число от 1 до N-1 обязательно имело мультипликативно обратный элемент.
А где доказательство существования генератора и как его находят? Опять же, почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?
— Гость (14/12/2011 04:45)
>На твоем картофельном поле есть мультипликативно обратный элемент?
Есть. Колорадский жук называется.
>А где доказательство существования генератора и как его находят?
Борзый мьсе любезно просит unknownа своими славами начать пересказывать учебник по теории групп? Это такой толстый троллинг? Для самых ленивых есть ещё википедия.
>Опять же, почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?
Исходя из общих соображений — чтобы набор не убывал, а только переупорядочивался. Алгебраически такая перестановка ещё и обратима, потому с ней проще работать.
не проще ли отказаться от чисел как от одного из её представлений и рассматривать криптографию как некую подобласть абстрактной алгебры?
Есть похожие направления, хотя не столь радикально сформулированные.
произведение таких элементов группы можно определить через "абстрактные стрелки"
К концу одной новости упоминается система MQQ[link1].
Когда надо будет "заземлить" криптографию в практическую область, после всех доказательств, можно придумать как оптимальней представлять элементы групп (ну или там других алгебраических структур) числами.
В этом одна из засад. В том, что напрямую эффективно ничего не посчитать, а когда пытаются сгенерировать такую абстрактную структуру, то делают это с помощью традиционных способов. Получается, что с помощью обычной группы генерируется более абстрактная группа и производятся некие прямые и обратные преобразования. Выигрыш в стойкости и скорости получается неочевидным (хотя теоретически возможен за счёт оптимизаций, что и привлекает исследователей), сложность системы при этом растёт вместе со всеми доказательствами. Хотя, перенос DH в группы эллиптических кривых — очевидный успех такого подхода.
>А где это так важно, чтобы любое число от 1 до N-1 обязательно имело мультипликативно обратный элемент.
Там где нужно поле. Хотя в RSA используется кольцо с экспоненциальными инверсиями, но порядок "фи" (p – 1)(q – 1) и здесь вылезает неслучайно. Также как ключ шифрования и расшифрования (ну прямо внезапно, да?) являются обратными множителями (мультипликативными инверсиями) по модулю фи. Т.е. не "простые числа, потому что RSA", а "RSA, DH и ещё куча всего невозможно без простых чисел".
>А где доказательство существования генератора
В следствиях из теорем Лагранжа и Эйлера.
>и как его находят?
Простого алгоритма нет. Есть эвристики и проверки.
>почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?
Не всегда важно. Важно знать порядок (цикличности) получаемой подгруппы.
Исходя из общих соображений — чтобы набор не убывал, а только переупорядочивался. Алгебраически такая перестановка ещё и обратима, потому с ней проще работать.
В DH можно (нужно) использовать генератор не всей группы (примитивный или первообразующий корень), а сильной подгруппы. Так и считать быстрее и стойкость сохраняется. При этом структура подгруппы будет определена свойствами простых чисел. Например, для сильного простого числа p=2q + 1 будет только четыре подгруппы. Тогда можно работать с заведомо сильной подгруппой порядка q. В реальности выбор подгрупп в DH ещё более заоптимизирован. Т.е. можно допустить, чтобы набор убывал, но надо точно заранее показать по порядку подгруппы, насколько он будет убывать. Чтобы не получить слабую подгруппу с малой цикличностью, защититься от атак навязывания слабых подгрупп, утечки информации о логарифме через вычисления по символу Лежандра.
Иногда бывает нужна цикличность всей группы. Как справедливо отмечено, это нужно там, где требуется обратимость.
— Гость (14/12/2011 15:45)
>Есть. Колорадский жук называется.
А кому он обратен? Твоей маме?
>Борзый мьсе любезно просит unknownа своими славами начать пересказывать учебник по теории групп?
Если дадите понятный и не слишком заучный учебник – буду благодарен. unknown, не то чтобы это была критика, но те, кто могут понять твой пост, вопросов задавать не будут.
xxx*: Я тебе могу напомнить историю, которую сейчас радостно всем рассказываю. xxx: К нам в общагу проникли какие-то гопы, поднялись на второй этаж, напоролись на тебя и спросили: "А тут девушки нормальные есть?" На что ты ответил: "А нормальные – это какие? Которые со своим сопряженным коммутируют?" Они профигели и тихо ответили: "Ну, как это, ну, в общем, да".
я: В упор не помню! Но вопрос "А тут девушки нормальные есть?" с большим трудом припоминается. xxx: Ну вот я запомнил, потому что ржал над этим оооооооооооочень долго. Девушкам рассказывай — пусть понимают, что такое быть нормальной[link3]!
— Гость (16/12/2011 00:12) А сами-то Вы как много прочли из этой книги? Впрочем, вводные главы там изложены популярней и доступней, чем в других книгах, которые я листал.
Где важны? В криптографии? Ну потому что вычислительно трудная задача — это именно факторизация большого числа, являющегося произведением двух больших простых чисел. Всё остальное факторизуется легко.
Сами простые числа имеют при этом достаточно случайное распределение.
Матапушта не Райвист, Шамир и Адлеман, а ещё Эйлер, Ферма, Галуа?
А о чём писать? Об алгебраической структуре, обладающей определёнными свойствами по модулю простого числа (DH) — группа, или полупростого числа — кольца и группы "по модулю фи" (RSA). Даже во всякой экзотике с решётками тоже простые числа.
Без простого числа элементарно не получить цикличность группы и конечность поля.
Когда нужны двоичные операции, то для GF(2n) определяют неприводимый полином — тоже простое число в полиномиальном виде.
Потому что другие числа представимы в виде произведения простых. А вообще вопрос сродни "почему здания строят из кирпечей". Ну технология такая!
Почему диффи-хеллман должен быть по простому модулю?
Имелось в виду "не отвечайте "потому что они используются в RSA", ценность такого ответа равна нулю", что я и написал в вопросе.
Напиши об этом. Я с математикой, стоящей за такого рода криптографией, знаком поверхностно.
Для понимания некоего стандартного набора криптоалгоритмов достаточного совсем небольшого числа базовых понятий из алгебры и теории чисел (всякие экспериментальные направления на экзотических алгебрах пока оставим в стороне). Естественно, сама по себе эта математика известна задолго до того, как её приспособили для криптографии.
Допустим, у нас есть простое число 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]
Это такой петросянистый юмор? Или академический снобизм?
На твоем картофельном поле есть мультипликативно обратный элемент?
Для группы по модулю N мультипликативно обратные элементы будут для всех взаимно простых с N чисел. А где это так важно, чтобы любое число от 1 до N-1 обязательно имело мультипликативно обратный элемент.
А где доказательство существования генератора и как его находят? Опять же, почему так важно, чтобы с его помощью можно было бы получить абсолютно все числа?
Есть. Колорадский жук называется.
Борзый мьсе любезно просит unknownа своими славами начать пересказывать учебник по теории групп? Это такой толстый троллинг? Для самых ленивых есть ещё википедия.
Исходя из общих соображений — чтобы набор не убывал, а только переупорядочивался. Алгебраически такая перестановка ещё и обратима, потому с ней проще работать.
Есть похожие направления, хотя не столь радикально сформулированные.
К концу одной новости упоминается система MQQ[link1].
В этом одна из засад. В том, что напрямую эффективно ничего не посчитать, а когда пытаются сгенерировать такую абстрактную структуру, то делают это с помощью традиционных способов. Получается, что с помощью обычной группы генерируется более абстрактная группа и производятся некие прямые и обратные преобразования. Выигрыш в стойкости и скорости получается неочевидным (хотя теоретически возможен за счёт оптимизаций, что и привлекает исследователей), сложность системы при этом растёт вместе со всеми доказательствами. Хотя, перенос DH в группы эллиптических кривых — очевидный успех такого подхода.
Там где нужно поле. Хотя в RSA используется кольцо с экспоненциальными инверсиями, но порядок "фи" (p – 1)(q – 1) и здесь вылезает неслучайно. Также как ключ шифрования и расшифрования (ну прямо внезапно, да?) являются обратными множителями (мультипликативными инверсиями) по модулю фи. Т.е. не "простые числа, потому что RSA", а "RSA, DH и ещё куча всего невозможно без простых чисел".
В следствиях из теорем Лагранжа и Эйлера.
Простого алгоритма нет. Есть эвристики и проверки.
Не всегда важно. Важно знать порядок (цикличности) получаемой подгруппы.
В DH можно (нужно) использовать генератор не всей группы (примитивный или первообразующий корень), а сильной подгруппы. Так и считать быстрее и стойкость сохраняется. При этом структура подгруппы будет определена свойствами простых чисел. Например, для сильного простого числа p=2q + 1 будет только четыре подгруппы. Тогда можно работать с заведомо сильной подгруппой порядка q. В реальности выбор подгрупп в DH ещё более заоптимизирован. Т.е. можно допустить, чтобы набор убывал, но надо точно заранее показать по порядку подгруппы, насколько он будет убывать. Чтобы не получить слабую подгруппу с малой цикличностью, защититься от атак навязывания слабых подгрупп, утечки информации о логарифме через вычисления по символу Лежандра.
Иногда бывает нужна цикличность всей группы. Как справедливо отмечено, это нужно там, где требуется обратимость.
А кому он обратен? Твоей маме?
Если дадите понятный и не слишком заучный учебник – буду благодарен. unknown, не то чтобы это была критика, но те, кто могут понять твой пост, вопросов задавать не будут.
Слово "троллинг" каждый определяет для себя, да?
Не поверишь – я там был.
Отправка в поле для наблюдения за картошкой не помогла, да? Что обязан делать солдат, чтобы пользоваться заслуженным уважением офицеров и прапорщиков воинской части?[link2]
Напомнило:
xxx: К нам в общагу проникли какие-то гопы, поднялись на второй этаж, напоролись на тебя и спросили: "А тут девушки нормальные есть?" На что ты ответил: "А нормальные – это какие? Которые со своим сопряженным коммутируют?" Они профигели и тихо ответили: "Ну, как это, ну, в общем, да".
я: В упор не помню! Но вопрос "А тут девушки нормальные есть?" с большим трудом припоминается.
xxx: Ну вот я запомнил, потому что ржал над этим оооооооооооочень долго. Девушкам рассказывай — пусть понимают, что такое быть нормальной[link3]!
*Cокомнатник по общежитию, мой третий курс.
Собственно, не несите пургу, придерживайтесь темы – и сравнения с гопами отпадут. Это я про поле с жуками.
Желающим научиться говорить умные слова рекомендую прочесть Голдблатт Р. Топосы. Категорный анализ логики[link4] Можете стать чуть умнее попугая ;)
А сами-то Вы как много прочли из этой книги? Впрочем, вводные главы там изложены популярней и доступней, чем в других книгах, которые я листал.
Оно имеет какое-то отношение к топику?