0으로 채워진 상태 배열에서 KECCAK은 어떻게 작동합니까?
Java에서 스폰지를 구현하려고합니다. 상태는 모두 0으로 구성된 빈 200 바이트 배열로 시작됩니다. NIST의 KMAC 샘플 문서에서 다음이 발생합니다.
(검은 색 선은 pdf 페이지 나누기)
Im이 이것을 읽는 방식은 많은 0이있는 상태가 KECCAK로 전송 된 다음 명백하게 임의의 데이터가있는 상태가 반환 된 것입니다. SHA3 / KECCAK는 빈 데이터를 임의의 데이터로 변환합니까? 여기서 올바른 질문을하고 있습니까? 도움을 주시면 감사하겠습니다.
답변
개인적 으로 Keccak.team Psuedo Code 문서는 Keccak-p를 이해하는 데 매우 유용합니다.
DannyNiu가 의견에서 말했듯이 대부분의 (모두?) 암호화 순열은 "라운드 상수"를 사용합니다. 이 상수는 어떻게 든 Keccak 상태에서 혼합됩니다.
의사 코드 문서는 라운드 상수를 테이블로 제공합니다.
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
그리고 그것들이 어떻게 사용되는지 설명합니다. iota 단계에서$n^\text{th}$ Keccak-p 라운드, $n^\text{th}$ 라운드 상수 $RC[n]$ 소개되고 첫 번째 단어 인 첫 번째 차선으로 XOR됩니다.
라운드 상수를 제외하고 Keccak 순열은 매우 좋은 확산을 가지고 있습니다. 초기 상태 어딘가에있는 단일 비트는 많은 출력 비트에 크게 기여합니다.
두 가지의 조합은 Keccak 순열 이 매우 무작위로 보인다는 것을 의미합니다 . 물론 유한 알고리즘이 그렇게 할 수 없기 때문에 0 엔트로피를 무작위로 바꿀 수는 없지만 Keccak의 목표는 사물을 혼합하고 무작위로 보이게 만드는 것입니다.
Keccak 순열 함수는 일반적으로 제로 입력 (모든 비트는 0)을 제로 출력에 매핑합니다. iota 단계가 아닌 경우 상태의 한 단어가 0이 아닌 상수와 함께 XOR됩니다.
완전한 확산을 위해 약 3 개 (24 개 중) 라운드이면 충분합니다. 즉, 상태의 모든 비트가 3 개 라운드 후에 다른 비트마다 영향을줍니다. 순열은 상태를 8 번 완전히 혼합한다고 말할 수 있습니다. 즉, 하나의 비트 만 1이면 상태 전체에서 빠르게 확산되어 3 라운드 후에 상태 비트의 약 절반이 1이됩니다.
허락하다 $R$예를 들어 모든 또는 거의 모든 비트가 동일한 값을 갖거나 짧은 비트 패턴이 정기적으로 반복되는 것과 같이 합리적으로 "정규보기"라고 할 수있는 상태 값의 집합입니다. 모두 중에서$2^{1600}$ 상태, 그 $R$아주 작은 부분입니다. 어떤 상태도$R$ 출력에 매핑됩니다. $R$. 이것은$|R| \ll 2^{800}$ ( "생일 역설"참조).
이는 정규적으로 보이는 출력에 매핑되는 규칙적인 입력이 없다는 것을 의미합니다. 그리고 주어진 상태가 출력에 매핑 될 확률$R$ 무시할 수 있습니다. 즉, 누군가가 순열의 역수를 계산하여 의도적으로 입력을 구성하는 것을 제외하고는 출력이 항상 무작위로 보입니다.