PHP에서 RSA 비공개 키를보다 빨리 계산하는 방법

Question

안녕하세요 저는 PHP로 RSA 알고리즘을 직접 구현해야합니다. 유일한 문제는 개인 키를 계산하는 부분입니다. 내 함수가 작동하는 방식은 임의의 숫자를 가져 와서 개인 키 공식에 맞는지 확인하는 것입니다. 이것은 잘 작동하지만, 유일한 문제는 매우 큰 숫자를 사용할 때 시간이 오래 걸리고 페이지 시간이 초과된다는 것입니다. 궁금 해서요. 난수 생성을 계속하지 않아도 구현할 수있는 더 좋은 방법이 있습니까? 다음은 필요한 코드입니다.

$decrypt = rand(1,($phi-1)); 
while(!private($decrypt, $encrypt, $phi)){ 
$decrypt = rand(1,($phi-1)); 
} 

... 

function private($decrypt, $encrypt, $phi) { 

if(($decrypt * $encrypt) % ($phi) == 1){ 
Return true; 
} 
else{ 
Return false; 
} 
} 

Answer 1

이 방법은 작동하지 않습니다. PHP 숫자 유형은 배정 밀도 부동 소수점 숫자이므로 53 비트 주변의 정수를 정확하게 나타낼 수 없습니다. 대부분 bcmath 또는 gmp과 같은 PHP 다중 정밀도 라이브러리를 사용해야합니다. 이것은 여전히 ​​빠르지는 않지만 적어도 정확한 결과를 줄 것입니다.

Answer 2

옵션 1 :

이 작업을 순차적으로 수행하는 것이 좋습니다. rand()는 이전에 사용한 번호를 찾을 수 있습니다. 귀하의 최대 금액은 10, 청구 된 수는 8 또는 4, rand()는 3,5,9,10362736910,1,3을받을 수 있다고 가정 해 봅시다. 5,6,3,7,8 대답을하기 전에. 순차적으로 실행하면 최대 10 번까지 호출 할 수 있습니다.

하지만 난수가 필요합니다. 따라서 임의의 숫자로 시작한 다음 순차적으로 히트가 될 때까지 순차적으로 증가시켜야합니다. 시작 지점에 따라 8을 얻을 수도 있고 4를 얻을 수도 있습니다.

옵션 2 : 그 후

은, 당신이 수학적으로 수있는 다른 솔루션이 있습니다. 난수로 시작하여 모듈러스가 무엇인지 계산하고, 1과의 차이 (음수 일 경우, $phi을 추가하십시오). 그런 다음 1에서 $decrypt까지 실행하여 modded가 1과 다른 차이를 찾은 다음 해당 값을 암호화하여 응답에 추가하십시오.

$decrypt = 7 
$encrypt = 9 
$phi = 3 
($decrypt * $encrypt) % ($phi) = 0 
$differenceInMod = 1 - ($decrypt * $encrypt) % ($phi) = 1; 
if ($differenceInMod < 0) { 
    $differenceInMod+=$phi; 
} 
for($i = 1; $i<$decrypt; $i++) { 
    if (($decrypt * $i) % ($phi) == $differenceInMod) { 
     $validEncrypt = $encrypt + $i; 
     break; 
    } 
} 

아마도 stright sequential (옵션 1)보다 빠르지는 않을 것입니다. 그러나 숫자는 더 작고 제한이 있습니다.