Factor 명령이 RSA 계수에 대해 의미 없는 결과를 생성하는 이유는 무엇입니까?

알았어, 내 생각엔 내가 뭔가...뭔가 결점을 발견한 것 같아. 솔직히 모르겠어요. 이것은 매우 이상한 장면입니다.

저는 친구를 위한 개념 증명 프로젝트로 매우 작은 비대칭(RSA) 암호화를 해독하려고 합니다. RSA에 대해 잘 모르는 분들을 위해 여기서 중요한 사실을 살펴보겠습니다. RSA를 이미 알고 있다면 다음 단락을 건너뛰십시오.

RSA는 비대칭 암호화 알고리즘(공개/개인 키 암호화라고도 함)입니다. 이는 공개 키와 개인 키의 두 가지 키가 있음을 의미합니다. 둘 중 하나를 암호화에 사용할 수 있지만 다른 키만 복호화에 사용할 수 있습니다. 따라서 개인 키를 사용하여 작은 텍스트 파일을 암호화하면 공개 키로만 해독할 수 있습니다. 이는 키 교환에 유용합니다. 이는 소인수 분해라는 수학적 원리를 사용하여 수행됩니다(사실 두 개의 소수를 곱하는 것은 쉽지만 곱에서 원래의 두 소수를 제외하는 것은 어렵습니다). 공개 키는 암호화할 수 있지만 개인 키만 해독할 수 있다고 상상해 보세요. 개인 키에는 2개의 소수가 포함되어 있고, 공개 키에는 이 2개의 소수의 곱(모듈러스)이 포함되어 있습니다. 공개 키로 암호화된 데이터를 해독할 수 있는 유일한 방법은 모듈러스를 다시 2개의 소수로 분해하고 개인 키를 리버스 엔지니어링하는 것입니다. 그것이 제가 하려는 일이지만 아주 작은 규모입니다.

그건 그렇고, 소인수분해! 이것이 내가 하는 일이다. 나는 128비트 RSA 키를 생성했습니다(비대칭 암호화 측면에서 작습니다. 특히 내 노트북의 2GHz 프로세서가 1초 이내에 계산한다는 점을 고려하면 더욱 그렇습니다). 모듈러스를 추출하고 16진수에서 10진수로 변환할 때 잘못된 명령을 사용했는데(bc를 사용할 때 ibase를 선택하는 것을 잊어버렸습니다) 결과는 97964999429910939982995739699617이었습니다. 그런 다음 Factor 명령을 사용했습니다.

여기서 상황이 흥미로워집니다.

내가 그것을 분해하면 나는 얻는다.8대답은 내가 기대했던 2가 아닙니다.

97964999429910939982995739699617：3 3 3 17 433 613 937 858164002128703934431

지금 생각해보면 왜 두 가지 답을 얻지 못했는지 이해가 됩니다. 이것은 RSA 키 쌍의 실제 모듈러스가 아닙니다. 그러나 그것은 내가 발견한 "버그"가 아닙니다(그렇지 않으면 여러분은 이 글을 읽고 있지 않을 것입니다).

다시 확인하기 위해 이 숫자를 곱하여 모듈러스를 다시 얻기로 결정했습니다.

나는 명령을 사용했다

에코$((3*3*3*17*433*613*937*858164002128703934431))

글쎄요, 그러면 확실히 시작 번호가 다시 생성될 것입니다. 그렇죠? 97964999429910939982995739699617이 되어서는 안 될 이유가 없습니다.

글쎄요, 제가 8628928582186374751라는 답을 얻기 전까지는 그게 제 생각이었습니다.

이 명령이 왜 그렇게 명백히 잘못된 대답을 반환하는지 전혀 모르겠습니다. 어떻게 부정적일 수 있나요? 이것이 로컬 수학 함수의 결함입니까? Factor 명령이 정확합니다. 실제 물리 계산기(TI-84)를 사용하려고 시도했을 때 원래 인수분해한 값이 반환되었기 때문에 이것을 확실히 알고 있습니다.

나는 먼저 내 노트북(Kali Linux 실행)에서 이 명령을 시도했습니다. "uname -rvo" 명령은 "4.3.0-kali1-amd64 #1 SMP Debian 4.3.3-5kali4 (2016-01-13) GNU/Linux")를 알려줍니다. 그런 다음 고등학교의 Gentoo 서버에 원격으로 연결하고 동일한 명령을 실행했습니다. 다시 말하지만, 분명히 잘못된 답변입니다. Uname은 "4.1.15-gentoo-r1 #2 SMP Fri Mar 11 15:12:48 CST 2016 GNU/Linux"라고 말했습니다.

이건 뭐죠?