Security Lab



Поиск  Пользователи  Правила 
Закрыть
Логин:
Пароль:
Забыли свой пароль?
Войти  
Форум » Для программистов и разработчиков » Криптография и защита информации
Страницы: 1
RSS
Возведение в большую степень. (RSA)
 
#1
Это нравится:0Да/0Нет
03.06.2005 09:14:04
Помогите разобратся!
По какому приципу большие числа возводятся в большую степень? (алгоритм RSA)
Вроде идёт некая манипуляция уже непосредственно с булевыми значениями чисел... :\

PS. смотрел коды на Си, конечно ничего не понял :)
 
 
 
#2
Это нравится:0Да/0Нет
03.06.2005 09:24:38
Тебе код возведения в степень неясен или именно математическая часть?
 
 
 
#3
Это нравится:0Да/0Нет
03.06.2005 09:43:29
2Mr.Clumsy
для начала хотелось бы разобраться с математической частью
 
 
 
#4
Это нравится:0Да/0Нет
03.06.2005 11:04:46
гыгыгы нашел :)
Тут

Цитата:
Цитата
В этой процедуре используется известный метод возведения x в n-ую степень с использованием двоичного представления числа n. Для понимания метода рассмотрим пример. Пусть нужно возвести x в 11 степень. 11 = 1011 в двоичном коде. Тогда x^11 = x * x ^ 2 * x ^ 8. И x^11 mod n можно представить так: (x^ 8 * ((x^2 * (x mod n)) mod n)) mod n. Теперь нам необходима функция, выполняющая действие (a * b) mod n - mod_mult(a, b, n)....


...Так как х возводится в степени двойки, то операцию возведения в k степень можно заменить операцией побитового сдвига влево на k позиций. То есть x^11 mod n равносильно следующему: (x << 8 * ((x << 2 * (x mod n)) mod n)) mod n. x << k же равносильно x << 1 (x.shift_left()), выполненному k раз.

Остаток же от деления вычисляется как r -= n (как только r >= n).
 
 
 
#5
Это нравится:0Да/0Нет
03.06.2005 11:07:01
а теперь все это на PHP реализовать бы :) Если кто уже делал - код в студию пжлста!
 
 
 
#6
Это нравится:0Да/0Нет
05.06.2005 18:44:05
так вроде бы имеюца готовые либы для работы с RSA... www.php.net в руки и вперёд.
 
 
 
#7
Это нравится:0Да/0Нет
06.06.2005 08:36:17
Цитата
.cens пишет:
так вроде бы имеюца готовые либы для работы с RSA... www.php.net в руки и вперёд.

Есть. Но что они мне дадут?! (читаем вопрос ещё раз)
 
 
 
#8
Это нравится:0Да/0Нет
06.06.2005 13:32:33
Так тебе нужно именно возведение в степень? или работа с RSA?
для степени - вот такую хрень я накидал...
Код
<?php
&nbsp;&nbsp;&nbsp;&nbsp;print alt_pow(3,11);

&nbsp;&nbsp;&nbsp;&nbsp;function alt_pow($x, $power)
&nbsp;&nbsp;&nbsp;&nbsp;{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $res = base_convert($power, 10, 2);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $result = $x;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $t = strlen($res);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for ($i = 1; $i < $t; $i++)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;$digit = $res[$i];
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;if ($digit != 0)
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;  $result = $result * $result * $x;
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;else
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;  $result = $result * $result;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return $result;
&nbsp;&nbsp;&nbsp;&nbsp;}
?>



непонятно только вот это
Цитата
Так как х возводится в степени двойки, то операцию возведения в k степень можно заменить операцией побитового сдвига влево на k позиций.
сдвиг влево на k позиций - есть умножение x на (2^k), а совсем не возведение x в степень k
 
 
 
Страницы: 1
Читают тему