시계(크립토그래피)

Clock (cryptography)
폴란드 암호국
비루로 지프루프
방법 및 기술
위치
인원
부원장
라디오 인텔리전스 최고 책임자
독일 부문장
막시밀리안 시셰키
러시아 과장
얀 그랄리우스키
러시아 섹션 암호학자
피오트르 스몰레스키
에니그마
암호기
Enigma-logo.svg

암호학에서 이 시계는 폴란드 총참모부 암호국의 수학자-암호학자 제르지 로지키(Jerzy Rożycki)가 독일 에니그마 암호의 암호 해독을 용이하게 하기 위해 고안한 방법이었다.이 방법은 서로 다른 회전 자세를 이용하여 독일 에니그마에서 가장 오른쪽 로터를 결정했다.폴란드인의 경우 가장 오른쪽 로터를 학습하면 로터 순서 검색 공간이 3배(로터 수)로 줄어들었다.영국인들은 방법을 개선했고, 그것은 제한된 수의 폭탄을 더 효과적으로 사용할 수 있게 했다(영국인들은 5~8개의 로터에 직면했다).

방법

이 방법은 때때로 에니그마 기계의 로터 중 어느 것이 맨 오른쪽에 있는지, 즉 키가 눌릴 때마다 로터가 항상 회전하는 위치에 있는지를 판단할 수 있게 했다.[1]시계법은 1933-1935년에 예지 로이키에 의해 개발되었다.[2]

Marian Rejewski의 그릴 방법은 우측 로터를 결정할 수 있지만, 가능한 로터 순열(당시에는 3개의 로터가 있었다)을 26개의 회전 가능한 회전 각각에서 시도해야 한다.그릴 방식 테스트도 플러그보드 설정에 의해 복잡해졌다.대조적으로, 시계 방식은 플러그 보드의 영향을 받지 않는 간단한 테스트를 포함했다.[3]

1930년대 초 독일인들이 한 번에 3개월씩 같은 로터 주문을 사용했기 때문에 로터 순서를 결정하는 것은 큰 부담이 되지 않았다.로터 순서는 한 번 결정할 수 있고, 그 다음 3개월 동안 사용할 수 있다.1936년 2월 1일, 독일인들은 매달 로터 순서를 바꾸었다.1936년 11월 1일, 독일인들은 매일 로터 순서를 바꾸었다.[4]

로지키의 '시계' 방법은 훗날 영국의 암호학자 앨런 튜링(Alan Turing)이 Bletchley Park에서 '반부리스무스(Banburismus)'라는 암호기술을 개발하는 과정에서 정교하게 다듬어졌다."[5]

배경

암호국은 에니그마 기계에 의해 봉쇄된 독일의 무선 교신을 받았다.약 60개의 메시지로, FBI는 메시지 키 인코딩을 위한 마리안 레제프스키의 특징적인 구조를 결정할 수 있었다.[6]빈약한 메시지 키를 이용하여, FBI는 메시지 키 인코딩을 결정할 수 있었다.그 시점에서 암호 분석가들은 메시지 키와 그들의 암호문만 알 수 있을 것이다.그들은 플러그보드 설정, 링 설정, 로터 순서 또는 초기 설정과 같은 일일 키의 다른 비밀을 모를 수 있다.그렇게 적은 정보와 약간의 운으로 폴란드인들은 여전히 어떤 로터가 가장 오른쪽인지 판단할 수 있었다.

매일의 트래픽에서, 메시지 키가 같은 두 글자로 시작하는 메시지 쌍이 십여 개 있을 수 있다.[7]즉 좌회전자와 중전회전자가 같은 위치에 있다는 뜻이다.

메시지 쌍의 암호문을 정렬하는 방법에는 두 가지가 있다.[8]두 선형 모두 시도되며, 선형 중 하나는 동일한 폴리 알파벳 대체를 사용한다.그것으로부터, 암호 촉매는 특정한 문자 범위 내에서 발생한 로터 회전율을 결정할 수 있다.

로터스는 이직 포지션이 달랐다.영국인들은 로터 1세가 R에서, 로터 2세가 F에서, 로터 3세가 W에서, 로터 4세가 K에서, 그리고 다른 모든 로터가 A에서 뒤집히는 것을 의미하는 니모닉 "로얄 플래그 웨이브 킹스 위"를 사용하였다.

만약 메시지 쌍이 협력한다면, 폴란드인들은 이직률이 발생하는 창을 하나의 로터만 포함하도록 좁힐 수 있다.한 메시지 쌍은 창 B에서 U로 교체되었다고 말할 수 있다; 그것은 로터 I(R), II(F), IV(K)가 실행 가능하다는 것을 의미했다.두 번째 메시지 쌍은 M에서 C까지의 창을 생성할 수 있다. 즉, 로터 I(R), III(W), V+(A)가 실행 가능하다는 것을 의미한다.로터 1만이 두 메시지 쌍을 모두 만족하므로 로터 1은 우측 로터가 된다.

기계 설정

에니그마 암호기는 사용자들이 몇몇의 공유된 비밀을 가지고 있는 것에 의존했다.1930년식 에니그마 설명서의 일일 비밀 설정은 다음과 같다.[9][10]

일별 설정(공유 암호):로터 순서 : III III 링스텔룽 : 24 13 22 (XMV) 반사경 : A-M, F-I, N-V, P-S, T-U, W-Z 그룬스텔룽 : 06 15 12 (FOL)

일일 설정은 메시지를 교환할 수 있도록 기계를 구성하는 방법을 코드 사무원에게 알려주었다.처음에 기계에는 어떤 순서(휠 순서 또는 로터 순서)로 배열할 수 있는 3개의 로터가 있었다.[11]각각의 로터는 숫자나 문자가 새겨진 링을 가지고 있었고, 그 링은 26개의 위치 중 어느 하나에 있을 수 있었다.플러그 보드는 추가 문자를 교환했다.

각 메시지에 대해 운영자는 메시지 본문을 암호화하기 위해 3글자 메시지 키를 선택한다.의도는 이 키가 무작위로 되는 것이었고, 각 메시지에 임의의 키를 사용하는 것은 좋은 보안 관행이었다.수신자가 메시지를 해독할 수 있도록 메시지 키를 수신자에게 전달해야 함.

메시지 키를 클리어로 보내는 대신, 메시지 키는 그룬스텔룽(접지 설정)으로 암호화된다.심각한 절차상의 실수로 독일인들은 메시지 키를 두 번 암호화했다.만약 메시지 키가 "ABL"이라면, 독일인들은 두 개의 키 "ABLABL"을 암호화하여 결과를 전송한다("PKPJXI").메시지 키를 두 번 보내면 전송에 장애가 있는 키가 복구될 수 있었지만, 암호 실수는 암호화된 키를 두 번 보내는 것(예: "PKPPKP")이 아니라 두 번 된 키를 암호화하는 것이었다.그 두 개의 열쇠는 폴란드에게 공격을 가했다.만약 동일한 일일 키(약 70개의 메시지)를 사용하는 메시지 트래픽이 충분하고 코드 사무원들이 약한 키(예: "CCC" 또는 "WER")를 사용한다면, 폴란드인들은 르제우스키의 특성 방법을 사용하여 하루 동안의 메시지 키를 모두 결정할 수 있을 것이다.놀랍게도 폴란드인들은 플러그보드 설정, 로터 순서, 로터 위치, 링 설정 등 일상적인 기계 설정의 실질적인 비밀을 배우지 못한 채 메시지 키를 끊었다.

폴란드인들은 그 남은 비밀들을 얻기 위해 다른 기술들을 사용해야 했다; 시계법은 로터 순서를 결정하는 데 도움을 주었다.

에니그마 로터회전 노치는 13에 가까운 좌측 로터에서 볼 수 있다.중앙 근처에 우측 로터 표시가 있는 것은 로터 II임을 나타낸다.

회전 장치마다 회전 위치가 다름

주요 기사:에니그마 로터 디테일

시계 방식은 회전 위치가 다른 3개의 회전 장치(I, II, III)를 활용했다.각 문자가 암호화된 상태에서 가장 오른쪽 로터가 움직였다.링의 특정 위치에서 문자를 암호화하면 다음 로터가 왼쪽으로 한 위치(회전)로 이동하게 된다.다음 로터가 움직이게 하는 링 위치는 각 로터마다 달랐다: 로터 I는 Q-R 전환에서 전진("로열"), 로터 II는 E-F에서 전진("플래그"), 로터 III는 V-W에서 전진("웨이브")[12]했다.회전율을 감지할 수 있다면 가장 오른쪽 로터가 확인될 수 있다.

폴란드인들은 메시지 키에 금이 갔기 때문에, 링 위치가 메시지 키였기 때문에 각 메시지의 링 위치를 알고 있었다.[13]

트래픽이 충분하면 폴란드인들은 동일한 두 문자로 시작하는 메시지 키를 찾을 수 있을 것이다.폴란드인들이 "AAA"와 "AAT" 키가 있는 메시지를 받았다고 가정하자. 

Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Message Key AAT: SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX

우연의 일치 지수

충분히 긴 메시지의 우연 지수를 사용하여, 폴란드인들은 로터 설정이 일치하는 곳을 결정할 수 있었다.그 결정은 통계적이지만 또한 미묘하다.그것은 언어의 균일하지 않은 글자 빈도를 이용한다.글자가 정렬된 두 문장을 생각해 보아라.만약 문자의 빈도가 같다면, 첫 번째 문장의 문자는 두 번째 문장의 같은 위치에 있는 문자와 확률 1/26 (0.038)과 일치할 것이다.자연 언어의 경우, "e"와 같은 문자가 훨씬 더 가능성이 높기 때문에, 우연의 일치 가능성은 훨씬 더 높다.첫 번째 28자 안에 우연이 6개 있는 경우(26자당 예상 경기 수 1.73개보다 훨씬 높음)를 들 수 있다. 

WEHOLDITHSTOBESSELFEVIDENT * *** * *

비교되고 있는 두 문자열이 동일한 폴리 알파벳 키로 암호화되는 경우에도 우연의 일치 지수는 참이며, 문자가 동일하면 그 암호화 또한 동일하다.반대로 다른 폴리 알파벳 키로 문자열을 암호화하면 문자열이 랜덤화되고 우연지수가 무작위 일치(26자 중 1자)만 나타난다.

만약 두 개의 문자열이 충분히 길다면(예: 260자) 우연의 지수는 문자열이 동일한 폴리 알파벳 키(즉, 동일한 로터 구성)로 암호화되었는지 여부를 나타낼 것이다.

로터 위치 및 우연

우연의 일치 지수를 터무니없는 수준으로 강조하기 위해 위의 두 예시 메시지는 전적으로 "A"자로 구성되므로, 우연은 같은 로터 위치(정상 메시지에서는 일어나지 않을 일)를 공유하는 모든 위치에서 발생한다.그것은 짧은 메시지에서도 그 우연이 극명하게 드러나게 한다.실제로, 좋은 통계적 표시를 얻기 위해서는 긴 메시지가 필요하다.

폴란드인들은 매일의 트래픽을 검색하여 키가 같은 두 글자로 시작하는 한 쌍의 메시지를 찾아냈다.예: 키 쌍은 ("UIB", "UIW") 또는 ("GCE", "GCX")이다.메시지 키의 처음 두 글자가 다른 메시지의 키와 일치할 가능성은 작다(1/(26×26)=1/576). 그러나 일련의 메시지에서 그러한 한 쌍을 찾을 가능성이 있다; 그러한 한 쌍을 찾는 것은 생일 문제의 한 예다.

폴란드인들은 처음 두 글자가 일치하기를 원했다. 왜냐하면 그것은 왼쪽과 중간 로터가 동일한 회전 상태에 있고 같은 순열을 생산한다는 것을 의미하기 때문이다.폴란드인들은 또한 키의 세 번째 글자가 다르다는 것을 설명하기 위해 두 메시지를 정렬할 수 있다.위의 예("AAA", "AAT") 쌍을 볼 때, 폴란드인들은 메시지가 공통 키(공통 회전)를 공유하도록 메시지를 정렬할 수 있는 두 가지 가능한 방법이 있다는 것을 알았다.이 두 경우는 회전율(중간 로터 이동)이 "A"와 "T" 사이 또는 "T"와 "A" 사이에서 발생하는지 여부를 반영한다. 

A                  T right rotor pos: ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ Message Key AAA:  BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Message Key AAT:                     SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Coincidence:                         ========================================== 결론: 같은 키이므로 A-T에서는 이직률이 없다. 
T      A right rotor pos: TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS Message Key AAT:  SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX Message Key AAA:         BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG Coincidence:결론: 다른 키로 T-A에서의 전환

중간 로터는 가장 오른쪽(빠른) 위치에 있는 로터에 따라 다른 위치에서 회전한다.로터 I, II 및 III의 변경점은 1, 2, 3으로 표시된다.중간 로터의 위치는 우측 로터가 I, II 또는 III라고 가정하여 주어진다. 

Message Key AAA: BQWBOCKUQFPQDJTMFTYSRDDQEQJWLPTNMHJENUTPYULNPRTCKG turnover             2           1    3        2           1    3 Right           ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY Middle(I)       AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCC Middle(II)      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC Middle(III)     AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBCCC  Message Key AAT:                    SRDDQEQJWLPTNMHJENUTPYULNPRTCKGFHWQJTVQROVULGDMNMX turnover                              3        2           1    3 Right                              TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY중간 (I)AABBBBBB 중간 (Amiddle (I) AAABBBBBB Middle (ABBBBB)II) AAABABBBBBBBBBBBB 중간 (III)AABBBBBBBBBBBB 중간 (III)ABBBBBBBBBBBBBBBBBBBBBBBCCC

언어 기반의 우연이 일어나려면 세 개의 로터가 모두 일치해야 한다.그렇지 않으면 일반 텍스트가 임의로 스크램블되고 언어 속성이 표시되지 않을 것이다.우연이 일어나는 지역을 보면 어느 정도 관찰이 가능하다.만약 로터 1이 오른쪽에 있었다면, 중간 로터는 결코 일치하지 않을 것이고 우연의 일치 지수는 우연을 나타내지 않을 것이다.만약 로터 II가 오른쪽에 있다면, 중간 로터 또한 결코 일치하지 않을 것이다.로터 III는 완전한 합의를 보여준다.따라서 가장 오른쪽 로터는 로터 III가 될 것이다.

이 시점에서 폴란드인들은 오른쪽 로터가 III이고 로터 순서는 (I, II, III) 또는 (II, I, III) 중 하나라는 것을 알게 될 것이다.그들은 메시지 키를 알고 있었지만, 링 설정을 알지 못했기 때문에 로터의 절대 위치를 알지 못했다.그들은 또한 플러그보드 설정을 알지 못했다.폴란드인들은 그 정보를 배우기 위해 다른 방법을 사용할 수 있지만, 그러한 방법은 오른쪽 로터를 알면 단순화될 것이다.

효용

초기에는 시계법이 그다지 중요하지 않았다.1932년, 독일인들은 한 번에 3개월 동안 같은 로터 주문을 유지했다.1936년 2월 1일, 독일인들은 매달 로터 순서를 바꾸었다.일일 휠 순서 변경은 1936년 11월 1일부터 시작되었다.[14]

1936년 10월, 독일인들은 플러그의 수를 6개에서 8개로 늘렸고, 그것은 그릴 방법을 복잡하게 만들었다.폴란드인들은 사이클로미터와 카드 카탈로그를 개발했다.새로운 방법은 1년 동안 준비되지 않았지만, 거의 작업하지 않고 전체 로터 순서(우측 로터만이 아님)를 파악했다.[15]불행하게도, 그 카탈로그는 1937년 11월 2일 독일인들이 반사경을 바꾸었을 때 쓸모 없게 되었다; 새로운 카탈로그가 만들어져야 했다.

1938년 9월 15일, 독일인들은 네트워크상의 메시지가 같은 그룬스텔룽을 사용하지 않도록 절차를 변경했다.[16]그 변화는 더 이상 메시지 키가 쉽게 알려지지 않았기 때문에 시계 방법을 복잡하게 만들 것이다.

영국의 코드브레이커들은 시계법을 연장했다; Banburismus를 참조하라.독일 해군 에니그마 메시지는 같은 그룬스텔룽을 사용했으며, 영국의 암호 해독자들은 암호화된 메시지 키를 결정할 수 있었다.암호화된 키의 마지막 문자를 제외한 모든 문자가 일치하는 경우, 오른쪽 로터를 제외하고 동일한 로터 위치를 가질 수 있다.문제는 영국인들이 (폴란드인처럼) 일반 텍스트 메시지 키와 일치하지 않고 오히려 암호화된 메시지 키의 마지막 문자는 자연적인 "ABCDE..."를 가지고 있지 않다는 것이었다.WXYZ" 순서가 아니라 임의 순서.영국인들은 단 두 번의 오프셋을 보기보다는 가능한 모든 오프셋을 살펴 3번째 휠 순서를 충분히 유추해야 오른쪽 로터를 결정할 수 있었다.마지막 로터를 정확히 맞히면 영국인들이 귀중한 봄베 시간을 많이 절약할 수 있을 것이다.

메모들

  1. ^ 르제프스키 1984, 페이지 290
  2. ^ 르제프스키 1981, 페이지 223에 "이 기간 동안 로이키씨는 시계법이라고 불리는 절차를 고안했다.많은 경우에 있어서, 그것은 우리에게 주어진 날짜에 드럼 N인 I, II, III 중 어느 것이 드럼 N이었는지, 즉 어떤 드럼이 기계의 오른쪽에 있는지를 결정할 수 있게 해주었다."
  3. ^ Rejewski 1981, 페이지 227은 "우리는 때때로 *시계 방법의 결과로 어떤 드럼이 위치 N에 있는지 알고 있었지만, 현재 SD 네트워크에 적용할 수 있는 유일한 방법인 그리드 방법은 때때로 실패하였다.1939년 1월 1일 독일인들이 다시 순열 S에 의해 수정된 글자 쌍을 7개에서 10개로 늘렸기 때문에 실패했다."
  4. ^ 르제프스키 1981 페이지 223
  5. ^ Good 1993, 페이지 155
  6. ^ Rejewski 1981, 페이지 218은 "특징 구조 AD, BE, CF가 구축되기 위해서는 60개 정도의 시료에 대해 당일로부터 충분한 수의 메시지가 필요했다"고 기술했다.
  7. ^ Rejewski 1981, 페이지 223은 "충분히 많은 양의 암호화된 자료를 임의로 가지고 있으면, 우리는 보통 각 쌍에서 열쇠의 처음 두 글자가 동일한 반면, 세 번째 글자는 서로 다르다"라고 말했다.
  8. ^ 르제프스키 1981 페이지 223
  9. ^ "Archived copy". Archived from the original on 2014-10-30. Retrieved 2014-10-07.{{cite web}}: CS1 maint: 제목(링크)으로 보관, 1930 "Schlüselanleitung jur Chiffriermachine Enigma I" ["사이퍼 기계 'Enigma I'의 키 사용 지침"]]
  10. ^ 시뮬레이터로 확인할 수 있다.For example, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Select Enigma I, choose reflector A (at the time, the Germans only had one reflector), set the wheel order (II, I, III), set the rings (24, 13, 22), set the plugs (AM, FI, NV, PS, TU, WZ), activate the plugboard, and set the wheels to the ground setting ("FOL").입력란에 ABLABL을 입력하면 PKPJXI가 출력되어야 한다.
  11. ^ 나중에 3개 이상의 회전 장치들이 있을 것이다.
  12. ^ 영국은 이직 포지션을 기억하기 위해 니모닉을 사용했다: "왕실 깃발 웨이브 킹스 위".
  13. ^ 링 위치는 윈도우에 표시되는 것이며 링스텔룽(링 설정)이 아니다.
  14. ^ 르제프스키 1981 페이지 223
  15. ^ Rejewski 1981, 페이지 224–225
  16. ^ Rejewski 1981, 페이지 225

참조

  • Kozaczuk, Władysław(1984년), Kasparek, 크리스토퍼(교육.), 수수께끼:.어떻게 독일 머신 암호화 있었습니까 브로큰이고 어떻게 그것은 세계 대전에 연합군으로 책을 읽다 있었나 2, 메릴랜드 주:.대학 Publications 아메리카의 아이 에스비엔 978-0-89093-547-7 Wkręgu enigmy, 바르샤바, Książka 나는 Wiedza, 1979년의 A와 증원된 개정된 번역 부록과 마리안 Rejewski에 의해서 보완된다.
  • Rejewski, Marian (July 1981), "How Polish Mathematicians Deciphered the Enigma", Annals of the History of Computing, IEEE, 3 (3): 213–234, doi:10.1109/MAHC.1981.10033
  • Rejewski, Marian (1984), "The Mathematical Solution of the Enigma Cipher", in Kasparek, Christopher (ed.), Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, pp. Appendix E: 272–291, ISBN 978-0-89093-547-7
  • Good, Jack (1993), "Enigma and Fish", in Hinsley, F. H.; Stripp, Alan (eds.), Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, pp. 149–166, ISBN 978-0-19-280132-6