먼저 우리는 이브가 수동적이라고 가정해야합니다. 이 말은 그녀가 진실로 카드를 밥에게 보내고, 앨리스에게 돌려주는 것은 실제로 밥의 반응입니다. Eve가 데이터를 하나 또는 두 방향으로 변경할 수 있고 (그녀의 조치가 감지되지 않은 경우) 아무 문제가 없습니다.

(오래된 전통을 존중하기 위해 대화에 참여한 두 정직한 당사자를 앨리스와 밥이라고합니다. 본문에서 “당신”이라고 말했지만 내 실제 이름은 “앨리스”가 아니지만, 당신이 쓴 것처럼 응답 할 것입니다. 것을 앨리스는 밥의 전화 번호를 확인하고 싶어.)

간단한 (그러나 약한) 대답은 해시 함수를 사용하는 것입니다. Alice는 카드에 다음과 같이 씁니다. “전화 번호의 SHA-256 해시를 반환하십시오.” SHA-256 은 해시 함수에 관한 한 안전한 것으로 여겨지는 암호화 해시 함수입니다. 수작업으로 계산하는 것은 지루하지만 여전히 가능합니다 (각 작업이 추가, 단어 이동 또는 회전 또는 비트의 비트 조합 인 약 2500 32 비트 작업입니다 .Bob은 하루에 또는 그래서).

이제 약점은 무엇입니까? 암호화 해시 함수 인 SHA-256은 “사전 이미지”에 내성이 있습니다. 이는 해시 출력이 주어지면 해당 입력을 복구하는 것이 매우 어렵다는 것을 의미합니다 (이브가 직면 한 문제임). 그러나 “매우 어렵다”는 “가장 쉬운 방법은 무차별 대입 : 일치하는 것을 찾을 때까지 가능한 입력을 시도하는 것”을 의미합니다. 문제는 여기서 무차별적인 힘이 쉽다는 것입니다. 가능한 전화 번호가 많지 않습니다 (북아메리카에서는 10 자리 숫자, 즉 100 억에 불과합니다). 밥은 손으로 일을하고 싶어하지만 이브가 그렇게 제한되어 있다고 가정 할 수는 없습니다. 기본 PC는 초당 수백만 SHA-256 해시를 시도 할 수 있으므로 Eve는 1 시간 이내에 완료됩니다 (GPU를 사용하는 경우 5 분 미만).

이것은 일반적인 문제입니다. Bob이 결정 론적이라면 (즉, Alice의 특정 메시지에 대해 항상 동일한 응답을 반환 할 것임) Eve는 그를 시뮬레이션 할 수 있습니다. 즉, Eve는 전화 번호를 제외하고 Bob에 관한 모든 것을 알고 있으므로 사실상 전화 번호 만 다른 100 억 명의 Bob을 운영합니다. 그녀는 가상 밥 중 하나가 실제 밥이 실제로 돌려 준 것을 돌려주기를 기다립니다. 이 결함은 임의의 nonces 및 대칭 암호화와 관련된 많은 종류의 “스마트”솔루션에 영향을 미칩니다. 그것은 강력한 결점이며 그 근본 원인은 Eve와 Bob의 컴퓨팅 성능에 큰 차이가 있습니다 (Bob 도 Eve보다 큰 컴퓨터를 보유한 경우 느리게 사용할 수 있음)많은 반복을 사용하여 해시 함수; 암호 대신 전화 번호를 사용하여 암호 해싱이 어느 정도인지 확인하십시오. 참조 bcrypt 또한 이 답변을 ).

따라서 약하지 않은 솔루션 은 Bob에게 임의의 무작위성을 포함 해야합니다 . Bob은 동전을 뒤집거나 주사위를 반복적으로 던져서 계산에 값을 주입해야합니다. 또한 Eve는 Bob이 수행 한 작업을 공개 할 수 없어야하지만 Alice가 할 수 있어야하므로 일부 정보는 기밀 정보가 Bob에서 Alice 에게 전달 됩니다. 이것을 비대칭 암호화 또는 적어도 비대칭 키 계약이라고합니다. 계산하지만 여전히 합리적으로 안전한 해당 클래스의 가장 간단한 알고리즘은 PKCS # 1 v1.5 패딩을 사용한 RSA 입니다 . RSA는 을 공개 지수로 사용할 수 있습니다 . 따라서 프로토콜은 다음과 같습니다.e=3

$e = 3$

• Alice는 큰 정수 생성합니다. 여기서 와 는 비슷한 크기의 소수입니다. 따라서 의 크기는 보안을 보장하기에 충분합니다 (예 : 2012 년 현재 1024 비트 이상). 또한 Alice는 과 이 3의 배수가 되지 않도록 배열해야합니다 .p q n p − 1 q − 1n=pq

  $n=pq$

  $n = pq$p

  $p$

  $p$q

  $q$

  $q$n

  $n$

  $n$p−1

  $p-1$

  $p-1$q−1

  $q-1$

  $q-1$

• Alice는 카드에 을 씁니다 .n

  $n$

  $n$

• 밥은 제 패딩하는 만큼의 바이트 순서로 자신의 전화 번호를 00 02 XX XX … XX 00 BB BB .. (BB)의 10 바이트는 ‘BB’여기서 어떤 인코딩을 (PKCS # 1에 의해 기술이 의미하는 바와 같이, 전화 번호 및 ‘xx’는 0이 아닌 임의의 바이트 값이며, 이 1024 비트 정수인 경우 총 길이는 128 바이트 입니다.nn

  $n$

  $n$n

  $n$

  $n$

• Bob은 자신의 바이트 시퀀스를 큰 정수 값 (big-endian encoding) 으로 해석하고 (그래서 매우 큰 정수를 사용한 곱셈과 나눗셈, 결과는 나눗셈의 나머지). 그것은 여전히 ​​손으로 할 수 있습니다 (그러나 다시, 아마도 하루의 더 좋은 부분이 걸릴 것입니다). 그 결과 Bob은 Alice에게 다시 보냅니다.m 3 m o d nm

  $m$

  $m$m3 mod n

  $m^3\mathrm{m}\mathrm{o}\mathrm{d}n$

  $m^3 \mathrm{\ mod\ } n$

• Alice는 와 에 대한 지식을 사용 하여 Bob이 보낸 에서 을 복구 합니다. RSA 의 Wikipedia 페이지 에는 해당 프로세스에 대한 합리적인 설명이 있습니다. Alice가 가졌 으면 패딩을 제거 할 수 있으며 ( ‘xx’는 0이 아니므로 첫 번째 ‘bb’바이트는 분명하게 위치 할 수 있습니다) 그런 다음 전화 번호를 갖게됩니다.q m m 3 m o d n mp

  $p$

  $p$q

  $q$

  $q$m

  $m$

  $m$m3 mod n

  $m^3\mathrm{m}\mathrm{o}\mathrm{d}n$

  $m^3 \mathrm{\ mod\ } n$m

  $m$

  $m$

Alice의 계산에는 컴퓨터가 필요합니다 (컴퓨터가하는 일은 항상 초등적이고 수작업으로 수행 할 수 있지만 컴퓨터는 엄청나게 빠르기 때문에 실제로 “doable”은 너무 많은 시간이 걸릴 수 있습니다. 수동으로 RSA 해독 에는 많은 시간 이 소요됩니다 주).

(실제로 우리는 McEliece 암호화 를 사용하여 더 빠른 수동 계산을 할 수 있었지만 Alice가 카드에 쓰는 공개 키는 엄청날 것이며 카드는 단순히하지 않을 것입니다. 이브는 전체 책을 운송해야합니다 자릿수.)

답변