WikiProject Криптография / Информатика | (Номинальный стартовый класс, высокая важность) |
---|---|
WikiProject Computing / Программное обеспечение / CompSci / Безопасность | (Номинальный стартовый класс, малозначительный) |
---|---|
Эту статью необходимо переписать, чтобы пользователь без технических знаний мог ее понять.
В настоящий момент для обычного читателя, такого как я, это кажется такой ерундой. В нем используются неясные термины и ссылки на концепции, которые мало кто поймет.
Я бы сам попробовал это сделать, но так мало чего можно сделать, чтобы причинить больше вреда, чем пользы.
Может быть, тот, кто разбирается в предмете, готов изложить концепции простым английским языком?
Луций Элий Сеян ( разговор ) 14:03, 24 февраля 2016 (UTC)
Хороший пример конкретных параметров?
Пытался понять, что производит BBS и насколько быстро это будет на 32-битном процессоре.
Я пробовал эти параметры: M = 0xffffffe9 = 4294967273 = 10847 * 395959; р = 10847, фи (р-1) = 4480 = 2 ^ 7 * 5 * 7; q = 395959, phi (q-1) = 131984 = 2 ^ 4 * 73 * 113; gcd (phi (p-1), phi (q-1)) = 2 ^ 4 - не "большой", верно?
seed, конечно, не должно быть 0 или 1.
Тем не менее, начиная с семени 3, я получаю
9 81 6561 43046721 3793632897 2038349057 2324068865 120648705 1995565057…
Семена 5 и 7 работают аналогично ... Кажется, есть какие-то дополнительные требования к параметрам и / или семенам? Если я допустил глупую ошибку, код:
- у большинства семян точно такая же длина цикла, у некоторых семян нет, но нет сообщества (какие семена плохие ??)
#include #define NEXT(x) ((x)*(x)) % 0xffffffe9int main() { unsigned i = 7; while(1) { i = NEXT(i); printf("%u\n", i); } return 0;}
Погуглил некоторую информацию, относящуюся к BBS: http://www.ciphersbyritter.com/NEWS2/TESTSBBS.HTM
- Ваш M слишком велик для 32-битных целых чисел. (x) * (x) вызовет целочисленное переполнение, если x> 0xffff. Кажется, ваш код работает нормально при использовании 64-битных целых чисел. Уфретин 07:54, 10 января 2007 г. (UTC)
Сведение к проблеме факторинга
Распространенная ошибка - думать, что Блюм Блюм Шуб сводится к проблеме факторинга. Он сводится к задаче квадратичной остаточности . Просто не известно никакого способа решить эту проблему без факторизации модуля. Гарфилд Гарфилд ( разговор ) Гарфилд Гарфилд
Паритет
Анонимному редактору на 64.151.29.184: Я более или менее отменил ваше изменение, так как нашел ваше объяснение LSB (младший значащий бит) не очень ясным. Кроме того, я не знаю, что вы имеете в виду под выражением « x +1 n +1 ». - Джитсе Нисен, 12:06, 4 февраля 2004 г. (UTC)
- К сожалению, ваша очистка запутала некоторые вещи, но прояснила другие; суть оригинала заключалась в том, что вывод может быть получен из четности или из младших битов, а не в том, что это одно и то же. Я сделал все, что мог, чтобы прояснить это. Ваше здоровье. Эндрю Родленд 05:31, 28 августа 2005 г. (UTC)
Простите. Чтобы уточнить, под «битовой четностью» вы имеете в виду количество единиц в двоичном представлении? - Джитсе Нисен ( разговор ) 14:07, 28 августа 2005 г. (UTC)
- Да, это то, что я искал. Теперь я понимаю, что в оригинале могло просто подразумеваться значение «четности», указывающее на наименее значимый бит. Вы можете удалить «битовую четность x n или». Возможно, что четность в смысле бита четности используется для вывода BBS, но у меня нет оснований полагать, что это иное, чем мое (вероятно ошибочное) чтение предыдущей версии. Эндрю Родленд
Фактически, [1] говорит, что "вывод - это младший значащий бит или паритет ", так что ваше первоначальное прочтение, вероятно, все- таки было правильным. - Джитсе Нисен ( выступление ) 12:57, 31 октября 2005 г. (UTC)
Мне интересно, не является ли это неправильным толкованием, поскольку статья Сравнение двух генераторов псевдослучайных чисел , созданная Блюмом Блюмом и Шубом и связанная с этой статьей, определяет вывод как Parity (), затем позже определяет четность () как младший бит x (на странице 73) - 207.81.129.224 21:30, 15 ноября 2007 г. (UTC)
Симметричный или ассиметричный?
Я просматривал ссылки на этой странице, пытаясь найти ответ на этот вопрос. Нигде прямо не говорится, что алгоритм является симметричным или ассиметричным (мне было трудно найти ресурсы и определение алгоритма дешифрования, только упоминание китайского алгоритма остатка). Я предполагаю, что это симметрично, но из того, что я прочитал, я не могу сказать наверняка. Любая помощь будет оценена по достоинству. - Stux 15:34, 24 октября 2005 г. (UTC)
- Я не уверен, что вы подразумеваете здесь под «симметричным». Насколько я могу судить из статьи, алгоритм Блюма-Блюма-Шуба генерирует только (псевдо) случайные числа. Это не алгоритм шифрования и дешифрования текста. Приносим извинения, если это очевидно для вас, в этом случае я, вероятно, ничем не могу помочь. - Джитсе Нисен ( разговор ) 16:29, 24 октября 2005 г. (UTC)
- Не нужно извиняться, вы поднимаете хороший вопрос (и спасибо за быстрый ответ!) - все основные описания алгоритма перечисляют его как ГПСЧ , и не совсем понятно, как он будет использоваться для шифрования. Однако как в самой статье, так и на самой странице целочисленной факторизации они указаны как криптографические инструменты. Под «симметричным» я подразумеваю, если это инструмент для шифрования закрытого ключа (с использованием симметричного ключа) или шифрования открытого ключа (с использованием асимметричной пары / набора ключей) - Stux 17:56, 24 октября 2005 г. (UTC)
- Многие криптографические алгоритмы нуждаются в хорошем ГПСЧ . Он используется как в симметричном, так и в асимметричном шифровании. В асимметричных алгоритмах он используется для генерации больших простых чисел, в симметричных алгоритмах он используется для генерации случайных ключей (например, GPG генерирует случайный ключ, шифрует открытый текст с помощью симметричного алгоритма (например, AES), а затем отправляет зашифрованный случайный ключ с RSA). С этой точки зрения BBS - это просто «инструмент», который может использоваться любым алгоритмом, которому нужны случайные биты. В реальном мире BBS редко используется из-за того, что она слишком медленная, но есть алгоритм вероятностного шифрования Блюма-Голдвассера (который является асимметричным), который явно передается на BBS для генерации ключей. Извините за плохую грамматику и орфографию :-P. Если вам нужна дополнительная информация, вы можете связаться со мной на моей странице в Wikipedia Italia: - Иппацу ( разговор )
- Я хотел бы добавить, что, хотя это не алгоритм шифрования, он основан на оригинальной криптосистеме Рабина . Кстати, одно утверждение в статье может быть неверным (что мы пока не можем решить). Взлом RSA не так сложен, как факторизация модуля, поэтому в настоящее время нельзя сказать, что RSA привязан к проблеме факторизации, и поэтому генератор BBS может быть даже более безопасным, чем RSA. Однако его безопасность эквивалентна безопасности Рабина. - Эртугрул Сойлемез
- Об использовании генератора BBS для шифрования: его можно использовать как часть схемы шифрования с открытым ключом. Закрытый ключ - это пара , оба конгруэнтны 3 (mod 4); открытый ключ - это их продукт, целое число Блюма . Чтобы зашифровать -битовое сообщение , выбирается случайный и устанавливает , а также для ; затем передается зашифрованный текст где а также . Для расшифровки требуется и вычисляет с помощью китайской теоремы об остатках. В частности, пусть ; тогда . Так получатель может восстановить и поэтому другой и, следовательно, расшифровать сообщение. И наоборот, биты являются ядром карты возведения в квадрат по модулю , что является односторонним, если факторинг сложен. Следовательно вычислительно неотличимы от независимых равномерно случайных битов. Это доказывает смысловую безопасность конструкции. Он был представлен в работе М. Блюма и С. Голдвассера, «Эффективная вероятностная схема шифрования с открытым ключом, которая скрывает всю частичную информацию», CRYPTO '84.
Целые числа сложно "предположить" на множитель?
Я подумывал добавить внешнюю ссылку к задаче о призах P vs. NP Millenium в институте Клея, но гораздо проще добавить гиперссылку на фразу «целочисленная факторизация» на страницу Википедии с таким названием, поэтому я сделал это вместо этого, даже хотя в предыдущем предложении уже была другая ссылка на эту страницу.
Переместить страницу?
Мне не нравится название «Блюм Блюм Шуб» для этой страницы. Я думаю, что этот материал должен существовать в «генераторе псевдослучайных ошибок Блюма-Блюма-Шуба», потому что (1) это название дает понять, о чем статья, и (2) стандарт в криптографической литературе заключается в переносе имен авторов при написании, например . Обмен ключами Диффи-Хеллмана, криптосистема Голдвассера-Микали, Boneh-Franklin IBE и т. Д. На самом деле, теперь, когда я думаю об этом, я могу попробовать начать соглашение об именах для статей о криптографии, потому что многие из них названы плохо. Во всяком случае, поэтому я переместил страницу. Mangojuice 02:06, 21 января 2006 г. (UTC)
Возможная ошибка
Должна ли функция Big O быть "log log M" или это просто опечатка? Это должен быть журнал журнала M? Ноль 13:15, 12 сентября 2006 г. (UTC)
- Должен быть. Если бы это был просто логарифм M, мы бы смотрели на все биты модуля. 209.210.225.6 03:59, 3 февраля 2007 г. (UTC)
Обратите внимание на бесполезность доказательства безопасности
Безопасность генератора BBS доказана посредством сокращения, показывающего, что алгоритм, который успешно отличает вывод BBS от случайной строки (что эквивалентно предсказывает следующий бит) с немаловажным успехом, может быть использован для факторизации модуля. Однако это "сокращение" очень неэффективно. Фактически, как обсуждалось в разделе 6.1 Н. Коблитца и А. Менезеса, «Другой взгляд на« доказуемую безопасность , II », http://eprint.iacr.org/2006/229 , текущее снижение уровня безопасности почти полностью бесполезный. Для разумных в настоящее время размеров ключей (до 3072 бит) они демонстрируют защиту от злоумышленника, который использует не болеетакты. Да, это был минус. Вы должны отличать биты от случайных битов гораздо меньше, чем за один такт!
Еще одно предупреждение. Текущее доказательство показывает, чтобиты одновременно являются жесткими и поэтому могут быть извлечены на каждой итерации. В этом спрятано постоянное, и кажется, меньше единицы. Опять же, это обсуждается в статье Коблица и Менезеса.
Резюме: остерегайтесь асимптотических результатов. По крайней мере, с точки зрения безопасности они гораздо менее полезны, чем кажутся.
Ошибка в примере?
На странице написано, что а также должны быть простые числа, но в этом примере мне не кажется простым. Либо в примере допущена ошибка, либо описание алгоритма как-то вводит в заблуждение. - Самули, 1 сентября 2006 г.
- В этом примере есть еще одна ошибка. Для а также в результате будут биты b 0 b 1 ... b 5 = 1 0 0 0 0 0. Майкл Прагер 13:29, 15 ноября 2006 г. (UTC)
- Писатель, вероятно, имел в виду, что определяется с помощью битовой четности . Я пытался это прояснить. - Джитсе Нисен ( разговор ) 02:24, 16 ноября 2006 г. (UTC)
Математика толстая
Если я хочу понять пример, но понятия не имею, что означает фи. Как мне найти, что это означает в контексте? Это невозможно. —Предыдущий комментарий без знака добавлен 70.189.96.232 ( обсуждение ) 01:57, 26 февраля 2008 г. (UTC)
- Ссылка на символ уже дает его определение, т. е. статью о тотентной функции Эйлера . Но ссылку действительно легко не заметить. 85.2.120.226 ( разговорное ) 06:22, 26 февраля 2008 (UTC)
- Аккуратный. При первом упоминании. Теперь я это вижу. Я действительно попал на эту страницу раньше через список символов в вики, но отклонил его, потому что на этой странице он выглядит иначе. 70.189.96.232 ( разговорное ) 23:45, 26 февраля 2008 (UTC)
Реликвия исправлений?
В конце первого абзаца в «Пример»:
«В следующей таблице показаны разные выходные биты разных битов, используемых для определения выходных данных».
Возможно, это только я, но, насколько я могу судить, это не имеет смысла. Я, например, совершенно не могу понять, что это значит. Это был пережиток чьей-то доработки раздела? Может ли кто-нибудь, кто понимает, что это означает, исправить это?
- Я только что попытался прояснить это (и ответить на вопрос ниже). Wocky ( разговор ) 01:39, 5 ноября 2009 (UTC)
Но тогда кто был S?
В рассмотренном примере p = 11 q = 19 и s = 3. x-1 установлен на s, что такое s? если это произвольная переменная как p, q, тогда почему бы просто не сказать, что выбрана x-1. Иначе как насчет описания s? 86.132.9.254 ( обсуждение ) - Предыдущий недатированный комментарий добавлен в 21:09, 9 августа 2009 г. (UTC).
Ошибка в формуле расчета ?
Формула для расчета прямо заявляет, что
Однако в исходной статье формула имеет вид где - функция Кармайкла .
Поскольку M = pq, то, что не всегда равно (p-1) (q-1) (например, при p = 5 и q = 7, (p-1) (q-1) = 24, но lcm (p-1, q -1) = 12).
Есть ли проблема с моей математикой или статья неверна?
Спасибо. Rapidflash ( разговор ) 04:38, 10 ноября 2010 (UTC)
Непоследовательное / запутанное использование φ в резюме / примере
В сводке сказано, что p и q должны быть простыми числами, и что «gcd (φ (p), φ (q)) должен быть малым». Предполагая, что это правильно, это излишне сложно, потому что функция Euler_totient_function утверждает, что для простого p, φ (p) = p-1. Следовательно, это можно было бы более четко записать как «gcd (p - 1, q - 1)».
Пример, однако, относится к «gcd (φ (p - 1), φ (q - 1))». Я подозреваю, что это должно было быть «gcd (p - 1, q - 1)», поскольку это согласуется с «gcd (φ (p), φ (q))» выше. Стиви-О ( разговор ) 18:57, 23 сентября 2019 (UTC)
нет, произошла ошибка, это gcd (phi (p-1), phi (q-1)) - 77.157.180.59 ( talk ) 09:40, 2 декабря 2019 (UTC)
== Проблемы с длиной цикла == Привет всем, кто приходит с французской страницы в поисках дополнительной информации
Я рассчитал длину цикла для множества параметров,
все выглядит так, как будто идеальный размер цикла длины линейен по отношению к M, но по какой-то причине я получаю много падений в цикле длины для некоторых M
поэтому я смотрел только очень маленькие параметры M <1 000 000, но я смотрел их все, для нескольких семян
также бывает, что у меня есть падение цикла длины для некоторых семян, но это встречается реже. Мне было интересно, не пропустил ли я некоторые критерии помимо тех, которые перечислены в определении (2 простых числа в форме 4k + 3, с низким pgcd и семя не делится ни на p, ни на q, что еще?)
поэтому я не могу объяснить себе, почему цикл длины будет снижаться для некоторых специфических M, хотя они, кажется, следуют тем же правилам, что и другие, и менее значимы, но все же важны, почему некоторые семена ведут себя плохо, нет ли каких-то пропущенных условий в отношении не знаю "рассыпчатости" М
Я мог бы перейти к вычислению более высоких циклов, чтобы увидеть, сохраняется ли проблема, но будет все труднее и труднее вычислять длинные циклы ... так что я не продвинусь дальше, боюсь
Другая идея касается pgcd p-1 и q-1. Я придерживался pgcd = 2 и 6, это наименьшее значение, которое вы можете получить. Я ясно вижу, что когда pgcd = 2, он работает намного лучше, чем pgcd = 6, поэтому, возможно, если я начну работать с более высоким числом и сохраню свой pgcd как можно ниже, я улучшу линейную связь между M и длиной цикла ?? как я сказал в обсуждении, кому-то интересно, достаточно ли 2 ^ 4? ммм, я бы сказал нет, вроде лучше целиться на 2, не больше, но так ли это важно? С уважением
---РЕДАКТИРОВАТЬ---
вот несколько примеров, которые я вычислил для чисел RSA (M), которые, кажется, имеют очень короткие циклы (менее 1000) на случайных начальных числах.
124315108793 126682326977 132752243441 137778877289 138983498233 151990264421 141889257737 129159006553 130193764633 146808817637 150758144309 159121735673 175866224393 152536526057 1712117206237228227167227227407227227167227227169
Например
150758144309, что составляет 359291 * 419599, имеет цикл длины 180 по алгоритму BBS
так что должна быть какая-то причина
Например
151848964097, то есть 356819 * 425563, имеет цикл длины 391860, что по-прежнему не очень хорошо
но
151580636209, то есть 356819 * 424811, имеет цикл длины 4264260, что далеко не необычно, но все же лучше
РЕДАКТИРОВАТЬ № 2
Похоже, произошла небольшая ошибка при условии, что gcd (phi (p-1), phi (q-1)) должен быть маленьким, чтобы алгоритм был эффективным, возникает другой вопрос о том, как эффективно вычислять phi (p -1)