Mod n 암호 분석

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정확한 인용문을 도입하여 개선해주시기 바랍니다. (2017년 8월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인)

암호학에서 mod n 암호해석은 암호 차단 및 스트림에 적용할 수 있는 공격입니다.이것은, 등가 클래스(일치 클래스) 모듈로의 암호 동작 방법의 불균형을 이용하는 암호 분석의 한 형태입니다.이 방법은 1999년 John Kelsey, Bruce Schneier 및 David Wagner에 의해 처음 제안되었으며 RC5P(RC5의 변형) 및 M6(FireWire 표준에 사용되는 블록 암호 패밀리)에 적용되었습니다.이러한 공격은 페르마 소수에 대한 이진 덧셈과 비트 회전 모듈화의 특성을 이용했다.

RC5P의 Mod 3 분석

RC5P의 경우 modulo 3 분석을 실시하였다.암호에서의 연산(회전 및 덧셈, 둘 다 32비트 워드)이 일치 클래스 mod 3보다 다소 편향된 것으로 관찰되었습니다.접근방식을 설명하기 위해 왼쪽 회전을 1비트씩 고려합니다.

${\displaystyle X\lll 1=\left\{\begin{matrix}2X,&{\mbox{31}\\mbox{2X+1-2^{32},&{\mbox{31}\end{mbox}}}\오른쪽.}$

그럼, 왜냐하면

${\displaystyle 2^{32}\equiv 1gpmod {3},}$

따라서

$(\displaystyle X\lll 1\equiv 2X{\pmod {3}).}$

따라서 단일 비트 좌회전에는 간단한 설명 모듈로 3이 있습니다.다른 작업(데이터 의존 회전 및 모듈식 추가)을 분석해도 유사하고 주목할 만한 편견이 드러난다.연산을 조합하여 분석하는 몇 가지 이론적인 문제가 있지만, 편차는 전체 암호에 대해 실험적으로 검출될 수 있습니다.(Kelsey et al., 1999)에서는 최대 7라운드까지 실험을 수행했으며, 이를 바탕으로 이 공격을 사용하여 RC5P를 19~20라운드까지 구별할 수 있을 것으로 추측했다.대응하는 비밀키 회복 방법도 있습니다.

M6에 대해서는 mod 5와 mod 257의 공격이 더욱 효과적입니다.

레퍼런스

• John Kelsey, Bruce Schneier, David Wagner (March 1999). Mod n Cryptanalysis, with Applications Against RC5P and M6 (PDF/PostScript). Fast Software Encryption, Sixth International Workshop Proceedings. Rome: Springer-Verlag. pp. 139–155. Retrieved 2007-02-12.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
• Vincent Rijmen (2003-12-01). ""mod n" Cryptanalysis of Rabbit" (PDF). White paper, Version 1.0. Cryptico. Retrieved 2007-02-12. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
• Toshio Tokita; Tsutomu Matsumoto. "On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20)". Ipsj Journal. 42 (8).