Комментарии 15
Я в молодости реализовывал RSA с нуля, в качестве упражнения.
Использовал и сабжевые алгоритмы и ассемблерные вставки. На тогдашнем железе (2001г)
шифрование работало минуту. Генерация ключей — полдня. Мораль — крестьянских алгоритмов недостаточно. Для возведения в степень по модулю используют алгоритм Монтгомери (насколько помню, в Монтгомери-представлении вычисления ведутся по модулю степени двойки, то есть отбрасыванием старших разрядов). Для умножения больших чисел используют алгоритм Карацубы.
Использовал и сабжевые алгоритмы и ассемблерные вставки. На тогдашнем железе (2001г)
шифрование работало минуту. Генерация ключей — полдня. Мораль — крестьянских алгоритмов недостаточно. Для возведения в степень по модулю используют алгоритм Монтгомери (насколько помню, в Монтгомери-представлении вычисления ведутся по модулю степени двойки, то есть отбрасыванием старших разрядов). Для умножения больших чисел используют алгоритм Карацубы.
в части «Возведение в степень методом русских крестьян» в самом начале:
«Мы внесём в алгоритм два небольших изменения; оба будут касаться только колонки m.»
похоже, изменения касаются как раз колонки n.
То же самое в оригинале статьи.
«Мы внесём в алгоритм два небольших изменения; оба будут касаться только колонки m.»
похоже, изменения касаются как раз колонки n.
То же самое в оригинале статьи.
Эх, эту бы статью лет на 30 раньше. У нас один фрукт на кафедре для диплома запилил программку, которая работала на всех кафедральных ПК во время их «простоя» и записочку писал с просьбой её запускать (до быстрого возведения в степень он не додумался). А мне, в те же года, пришлось в исходниках PGP разбираться.
На первой картинке ошибка? Направление стрелочек нужно изменить на обратное?
Нет, все правильно.
Открытый текст шифруется с помощью публичного ключа, результат расшифровать возможно с помощью соответствующего секретного ключа
Открытый текст шифруется с помощью публичного ключа, результат расшифровать возможно с помощью соответствующего секретного ключа
Стрелочки работают в прямом и обратном направлении. Если я публикую открытый ключ -то все им шифруют, а расшифровать могу только я. При этом, когда я что-то шифрую закрытым ключом, то все могут расшифровать сообщение открытым и убедиться, что это именно я зашифровал.
Идея ровно в том, что тот, кто хочет послать зашифрованное письмо, шифрует его публичным ключом получателя. Все, теперь только адресат может его расшифровать, а значит сообщение можно передавать по незащищенным каналам связи.
А вот если поменять направление стрелочек, то потеряется сам смысл. Зашифрованное сообщение, которое может расшифровать любой ничем не лучше незашифрованного. Впрочем, если вы смогли расшифровать сообщение публичным ключом, значит оно было зашифровано приватным, а значит вы можете быть уверены, что письмо пришло от вашего собеседника, а не от левого лица. Примерно так работает цифровая подпись.
А вот если поменять направление стрелочек, то потеряется сам смысл. Зашифрованное сообщение, которое может расшифровать любой ничем не лучше незашифрованного. Впрочем, если вы смогли расшифровать сообщение публичным ключом, значит оно было зашифровано приватным, а значит вы можете быть уверены, что письмо пришло от вашего собеседника, а не от левого лица. Примерно так работает цифровая подпись.
Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.
А жаль, я бы почитал. Но за статью всё равно спасибо.
На практике значения M и по крайней мере или e, или d очень велики.
Уточню про d и e: когдя генерируют ключи RSA для шифрования, то специально берут маленькое e (потом вычисляют d, которое выходит большим). Смысл в том чтобы шифровать можно было быстро быстро, шифровать будут все чтобы отправить сообщение мне, а расшифровывать буду только я (вычисления становятся проще для большего числа людей), плюс еще и открытый ключ чуть короче выходит. Для электронной подписи всё ровно наоборот.
Для такого замечательного поста такая скучная картинка — преступление!
PatientZero, замените хотя бы на знаменитую картину Богдана-Бельского!
PatientZero, замените хотя бы на знаменитую картину Богдана-Бельского!
''Устный счёт в народной школе С. А. Рачинского'' (1895)
Если мы хотим найти n в степени m, то мы можем сделать это, перемножив m раз число n.
А не сравнивали ваш подход с бинарным возведением в степень? Там число операций умножения не более чем в 2 раза больше числа бит в m.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Криптография русского крестьянина