N 비트 크래킹 RSA 모듈 번호

Question

내 previous post와 관련이 있습니다.이 옵션은 비교적 약한 RSA 알고리즘을 사용하는 옵션이었습니다. 우리가 35 비트 숫자 (34359738367부터 34359738367까지)를 36 비트 모듈로 (34359738368에서 68719476735까지) 인코딩하려고한다고 가정합시다.

http://en.wikipedia.org/wiki/RSA을 참조하면 내 n이 34359738368 개에서 68719476735 개까지 (p-1 * q-1 형식)의 임의의 총합임을 알 수 있습니다. 임의의 d와 e를 선택합니다. 나는 숫자를 인코딩하고이를 UI에 표시합니다.

사용자는 최대 1,000 개의 출력을 볼 수 있다고 가정합니다. 폴라 (Polla)와 같은 알고리즘을 사용하여 내 d, ​​e 또는 n을 해독하여 새로운 수를 예측할 수 있습니까? 그렇다면 얼마나 힘들겠습니까? 예로서

(단지 알면 입력/출력 (1000 개) 세트를 말한다)

1. 1000162186531116156015
2. 1000162186633031668326
3. (입력/출력 형식 샘플로 6 개 출력을 고려) 10001621867,37351399313
4. 1000162186806071714212
5. 1000162186901188523761
6. 1000162187018341011998

누가 내 n, d, e가 무엇인지 말해 줄 수 있습니까? (N 사이 34359738368 upto 68719476735)

나는 그것이 얼마나 크랙 가능한지 알고 싶다. 그래서 내가 얼마나 오래, 얼마나 빨리, 얼마나 많은 출력을보아야하는지, 어떤 알고리즘을 사용할 수 있는지에 대한 정보를 줄 수 있다면 등등 그것은 좋을 것이다.

PS : 사용자는 표준 RSA 알고리즘처럼 "e"를 보지 못합니다. 그는 입력 출력 세트 만 볼 수 있습니다.

는 세부 내가 사용자에게 DB에서 순차적 사용자 ID를 제공하기 위해 노력하고 을 추가했습니다. 순차적이기 때문에 사용자가 몇 가지 등록을 수행하여 다른 사용자의 ID를 추측하지 못하게해야합니다. 이것을 피하려면 나는 < = 12 자리 숫자로 뒤섞어 야합니다. this question에 설명 된 많은 제약이있었습니다.

또한 n, d 및 e 값은 사용자에게 알려지지 않습니다. 사용자가 볼 수있는 최대 출력은 몇 가지 입력 샘플입니다 (반복 등록 방식으로)

"Jacobi"알고리즘을 사용하면 몇 초 내에 문제를 해결할 수 있기 때문에 Accipitridae가 답변을 수락합니다. n, e 또는 p를 모른 채.

Answer 1

공격자는 n 및 e mod (p-1)의 인수 p를 추측 할 수 있습니다. 각각의 추측은 메시지 m을 취하여 m^e mod p를 계산 한 다음 c mod p와 비교하여 확인할 수 있습니다. 여기서 c는 해당하는 암호문입니다. p와 e mod (p-1)는 각각 20 비트 일 수 있기 때문에,이 방식의 보안은 40 비트보다 크지 않다는 것을 의미합니다.

그러나 40 비트는 매우 조잡한 상한선입니다. 공격자가 훨씬 더 잘할 수 있습니다. 예를 들어 그는 p를 추측 할 수 있습니다. 그런 다음 그는 메시지와 암호문의 Jacobi 기호를 계산합니다. 메시지 m이 2 차 잉여 mod p이면, 암호문은 2 차 잉여 mod p이어야하며 그 반대도 마찬가지이다. 따라서이 관계가 메시지/암호문 쌍에 만족되지 않으면 그는 p에 대한 추측을 거부 할 수 있습니다. 또는 공격자는 메시지와 암호문 사이의 이산 로그를 계산할 수 있습니다. 이것은 e mod (p-1)에 대한 훨씬 빠른 후보를 제공합니다.

보안 수준이 20-30 비트 여야하므로 휴식 시간이 필요합니다. 샘플 수를 20으로 늘리면 몇 가지 벤치 마크를 시도 할 수 있습니다.

업데이트 : 실험을 실행하기 위해 20 개의 샘플을 제공하지 않았으므로 직접 생성해야했습니다. 다음 샘플을 입력으로

m = 10001621865 c = 31116156015 
m = 10001621866 c = 33031668326 
m = 10001621867 c = 37351399313 
m = 10001621868 c = 6071714212 
m = 10001621869 c = 1188523761 
m = 10001621870 c = 18341011998 
m = 10001621871 c = 7620400191 
m = 10001621872 c = 36106912203 
m = 10001621873 c = 37615263725 
m = 10001621874 c = 7795237418 
m = 10001621875 c = 34774459868 
m = 10001621876 c = 4555747045 
m = 10001621877 c = 33123599635 
m = 10001621878 c = 34836418207 
m = 10001621879 c = 33962453633 
m = 10001621880 c = 6258371439 
m = 10001621881 c = 7500991556 
m = 10001621882 c = 5071836635 
m = 10001621883 c = 911495880 
m = 10001621884 c = 39558568485 

으로, 전술 한 알고리즘은 인자에서 20ms의 201,821 및 206,153 를 찾는다. 설명한 바와 같이 e를 알 필요는 없지만 e = 65537은 추측하기 쉽고 악용 될 수도 있습니다.

RSA의 강점은 큰 정수를 인수 분해하는 어려움에 근거한다는 것입니다. 여기에서이 어려움을 제거하고 남아있는 것은 RSA의 모든 약점 (즉, 수학적 관계)입니다. RSA를 기반으로 한 블록 암호를 만드는 것은 끔찍한 생각입니다. 이전에 제안한 것처럼 Luby-Rackoff 구조를 사용하지 않으려 고하는 이유가 정말로 없습니다.

Answer 2

RSA는 Chosen-Ciphertext 공격에 취약합니다. 즉, 우리가 암호문 y를 깰 필요가 있다고 말하면, 암호문 - 평문 쌍 중 하나를 사용하여이를 해독 할 수 있습니다.

어떻게 그것을 깰 :

는 X0 및 Y0가 제공되었습니다 평문 - 암호문 쌍 인 X0 및 Y0을 선택합니다.

y1 = y0 * y mod ny1은이 기준을 만족하는 사용자에게 제공된 1000 개의 암호문 중 하나입니다. X1은 또한 주어진 Y1의 복호화이고, 이는 :

X1 = Y1^D 개조 N은

X1 = (Y0의 *의 예를 (이것은 우리에게 부여되어, 이미 X1 알고))^D 개조 N X1 = Y0^D *^D Y N 개의 개조 Ξ의 X0 * X

X1에서의 * X0^-1 = X

X가 Y의 복호이다.

물론 이것은 y0 * y mod n이 우리가 이미 가지고있는 다른 암호문을 생성하는지 여부에 달려 있으며 작업 할 수있는 1000 개의 쌍이 있기 때문에 깨지기 쉽지만 불가능하지는 않습니다. 당신은 단지 조심스럽게 매우 조심스럽게 선택해야합니다.

나는 또한 당신이 작업하고있는 n의 크기가 팩터링 경험적 방법을 사용하여 n의 프라임 분해를 상당히 빨리 찾을 수 있다고 덧붙이고 싶습니다. 또한 RSA는 타이밍 공격에 취약하지만 쉽게 저지 될 수 있습니다.

n/d/e를 모르는 상태에서 n, n과 e를 찾으려면 최소한 43,359,738,367 개의 n 개의 조합과 모든 조합의 e가 있어야합니다. 1000 개의 암호문 - 평문 쌍을 가진 사람이라도 n과 e를 해독 할 수있는 것은 쉽지 않습니다.

Answer 3

이것은 끔찍한 생각인데, 36 비트 RSA ?? 단순히 블록이나 스트림 암호를 사용하지 않는 것이 어떻습니까? 그렇게하면 1 : 1 매핑이 훨씬 안전 해집니다.

내가 권장하는 대체 솔루션은 UID로 SHA 해시를 사용하고 데이터베이스의 각 사용자에 대한 일련 번호를 별도의 열로 저장하는 것입니다.