전치 암호
Transposition cipher이 기사는 검증을 위해 추가적인 인용이 필요합니다. – (2008년 7월) (이 를 및 |
암호학에서 전치 암호(轉 transposition, )는 문자 자체를 변경하지 않고 문자의 위치를 스크램블링하는 암호화 방법입니다.전치 암호는 평문의 순열인 암호문을 생성하기 위해 일반 시스템에 따라 평문(일반적으로 문자 또는 문자 그룹) 단위의 순서를 바꿉니다.평문 단위의 위치를 변경하지 않고 단위 자체를 변경하는 대체 암호와는 다릅니다.전치 연산과 대체 연산의 차이에도 불구하고 ADFGVX 암호와 같은 과거 암호 또는 현대 AES(Advanced Encryption Standard)와 같은 복잡한 고품질 암호화 방법처럼 이들은 종종 결합됩니다.
일반원칙
일반 텍스트는 키를 사용하여 암호 텍스트로 재배열할 수 있으며, 지그소 퍼즐의 셔플 조각과 같은 문자의 순서를 스크램블링할 수 있습니다.결과 메시지는 문자를 배열할 수 있는 많은 방법이 있기 때문에 키 없이는 해독하기가 어렵습니다.
예를 들어, 일반 텍스트 "이 위키피디아"는 "TWDIP SIHII IKASE"로 암호화될 수 있습니다.공격자는 키 없이 암호화된 메시지를 해독하기 위해 가능한 단어와 구(예: DIATHESSESS), 분산(DISONSATE), 너비(WIDTH) 등을 추측할 수 있지만, 문자와 단어의 조합이 많기 때문에 평문을 재구성하는 데 시간이 다소 걸릴 수 있습니다.이와는 대조적으로 키를 가진 사람은 메시지를 쉽게 재구성할 수 있습니다.
CIP HER 키 14 5 3 2 6 시퀀스(가나다순 키) T IS IS 평문 IK I PEDIA * * * * 열별 암호문: #1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SE 가독성을 위한 그룹별 암호문: TWDIP SIHII IKASE
실제로, 이렇게 짧고 예측 가능한 키워드를 가진 메시지는 암호 분석 기술로 거의 즉시 깨집니다.전치 암호에는 몇 가지 취약성이 있으며(아래 "Detection and crypt analysis" 섹션 참조), 암호화 프로세스의 작은 실수로 암호문 전체가 무의미해질 수 있습니다.
그러나 긴 메시지(예: 100-200자 이상), 예측할 수 없는 내용, 메시지당 고유 키, 강력한 전치 방법 등과 같은 올바른 조건을 고려할 때 올바른 단어를 추측하는 것은 더 이상의 정보 없이는 계산적으로 불가능할 수 있습니다.엘론카 두닌과 클라우스 슈메는 암호를 파괴하는 역사적 암호에 관한 책에서 이중 기둥 모양의 전치(아래 참조)를 "알려진 최고의 수동 암호 중 하나"로 묘사했습니다.[1]
레일 펜스 암호
레일 펜스 암호는 암호화되는 방식에서 이름을 따온 전치 암호의 한 형태입니다.레일 펜스 암호에서 평문은 가상의 펜스의 연속적인 "레일"에 아래쪽과 대각선으로 쓰여졌다가 바닥에 이르면 위로 올라갑니다.그런 다음 메시지를 행 단위로 읽습니다.예를 들어, 세 개의 "레일"과 'WE ARE DISCOVERED FLAY ONCE" 메시지를 사용하여 암호 작성자는 다음과 같이 적습니다.
W. E. E. C. C. L. T. E. E. R. D. S. E. E. E. E. F. A. O. C. A. A. A. A. I. V. D. N.
그런 다음 읽어봅니다.
EOCAIVDEN에 대한 WECRLTEERD SOEF EOCAIVDEN
(암호는 오류를 방지하기 위해 이 암호문을 다섯 개의 블록으로 나눕니다.이것은 암호를 더 쉽게 읽을 수 있도록 만드는 데 사용되는 일반적인 기술입니다.공백은 일반 텍스트의 공백과 관련이 없으므로 일반 텍스트에 대한 정보를 전달하지 않습니다.)
스키테일
레일 펜스 암호는 고대 그리스에서 사용된 전치 암호를 만드는 기계적 시스템인 스키테일(SKIT-uhl-ee)과 유사한 패턴을 따릅니다.그 시스템은 실린더와 그 실린더를 감싸는 리본으로 구성되어 있습니다.암호화할 메시지는 감긴 리본에 적혀 있었습니다.리본이 원기둥에서 풀리면 원래 메시지의 글자가 다시 배열됩니다.그러나 리본이 암호화 실린더와 같은 직경의 실린더에서 휘어지면서 메시지는 쉽게 해독되었습니다.[2]이전과 동일한 예를 사용하여 실린더의 원주 주위에 세 글자만 들어갈 수 있는 반지름을 가진 경우 암호기는 다음과 같이 적습니다.
W.E.A.A.A.A.C.O.I.S.C.O.V.E.R.D.F.L.E.E.E.E.E.E.F.E.E.E.E.E.E.E.E.E.E.O.E.E.E.E.E.E.N.C.O.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.E.C.O.E.E.E.E.E.E.E.E.C.O.V.E.E.E.F.L.E.E.E.E.E.E.E.E.E.E.E.E.E.E
이 예에서는 실린더가 수평으로 작동하고 리본이 수직으로 감겨 있습니다.그래서 암호는 다음과 같이 읽습니다.
Woeevee DDNIF CSLEC의 초기 연구
경로암호
경로 암호에서 평문은 먼저 주어진 차원의 그리드로 작성된 다음 키에 주어진 패턴으로 읽힙니다.예를 들어, 레일 펜스에 사용했던 것과 동일한 평문을 사용하면 다음과 같습니다.
EE EE EE EE VE A DECX의 오류
키는 "내향, 시계 방향, 오른쪽 위에서 시작하는 나선"을 지정할 수 있습니다.그러면 다음과 같은 암호 텍스트가 제공됩니다.
EJXCTEDEC DAEWRIOR ONALEVSE
경로 암호는 철도 울타리보다 더 많은 열쇠를 가지고 있습니다.사실, 합리적인 길이의 메시지의 경우, 가능한 키의 수가 너무 많아서 현대 기계에서도 열거할 수 없습니다.하지만 모든 키가 똑같이 좋은 것은 아닙니다.잘못 선택된 경로는 과도한 평문 덩어리를 남기거나 텍스트가 단순히 반대로 바뀌게 되며, 이는 암호 분석가들에게 경로에 대한 단서를 제공할 것입니다.
경로 암호의 변형은 미국 남북전쟁 당시 연합군이 사용했던 유니언 루트 암호였습니다.이것은 일반적인 경로 암호와 유사하게 작동했지만, 개별 문자 대신 전체 단어를 바꾸어 사용했습니다.이것은 매우 민감한 단어들을 노출시킬 수 있기 때문에, 그러한 단어들은 우선 코드에 의해 가려질 것입니다.암호 서기는 암호문을 익살스럽게 만들기 위해 종종 선택된 전체 null 단어를 추가할 수도 있습니다.[citation needed]
주상 전치
기둥 모양 전치에서 메시지는 고정된 길이의 행으로 작성된 다음 열로 다시 읽고 열은 스크램블된 순서로 선택됩니다.행의 너비와 열의 순열 모두 일반적으로 키워드로 정의됩니다.예를 들어, 키워드는ZEBRAS의 길이는 6이고(따라서 행의 길이는 6), 순열은 키워드에 있는 문자의 알파벳 순서로 정의됩니다.이 경우 순서는 "6 3 2 4 1 5"가 될 것입니다.
정규 기둥 모양 전치 암호에서는 예비 공간이 널로 채워져 있고, 불규칙 기둥 모양 전치 암호에서는 공백으로 남아 있습니다.마지막으로, 메시지는 키워드에 의해 지정된 순서대로 열로 읽힙니다.예를 들어 ZEBRAS라는 키워드와 WE DISCOVERED라는 메시지를 사용한다고 가정해 보겠습니다. 한 번에 도망쳐보세요.규칙적인 주상 전치에서 다음과 같이 그리드에 기록합니다.
6 3 2 4 1 5 WE ARE COVE FLEATE TO EQ JEU
5개의 null(QKJEU)을 제공할 경우, 이 문자들은 메시지의 일부가 아닌 불완전한 열만 기입하기 때문에 임의로 선택할 수 있습니다.암호문은 다음과 같이 읽힙니다.
EVLNE ACDTK ESEAQ ROFOJ DEECU 와이어
비정규적인 경우 열은 null로 완성되지 않습니다.
6 3 2 4 1 5 WE AREED COVE COVE TO CECE
그 결과 다음과 같은 암호문이 만들어집니다.
EVLNA CDTES ODEC 와이어리스
그것을 해독하기 위해서 수신자는 메시지 길이를 키 길이로 나누어 열 길이를 계산해야 합니다.그런 다음 메시지를 열로 다시 작성한 다음 키워드를 수정하여 열 순서를 변경할 수 있습니다.
변형된 경우 메시지는 키 길이가 긴 세그먼트로 차단되고 각 세그먼트에 동일한 순열(키에 의해 제공되는)이 적용됩니다.이는 판독값이 열이 아닌 행 단위로 표시되는 기둥형 전치와 같습니다.
기둥 전치법은 적어도 1950년대까지 더 복잡한 암호의 구성 요소로서 진지한 용도로 계속 사용되었습니다.
이중 전치
단일 기둥 형태의 전치는 가능한 열 길이를 추측하고, 메시지를 열에 기록한 다음(키가 아직 알려지지 않은 것처럼 잘못된 순서로) 가능한 애너그램을 찾아 공격할 수 있습니다.그래서 더 강하게 만들기 위해, 이중 전치가 종종 사용되었습니다.이것은 단순히 두 번 적용된 주상 전치입니다.두 위치에 동일한 키를 사용하거나 두 개의 다른 키를 사용할 수 있습니다.
이중 전치의 시각적 시연
다음 예제에서는 JANAUSTEN과 AEROLANES 키를 사용하여 다음과 같은 평문을 암호화합니다. "변환 암호는 퍼즐 조각처럼 글자를 뒤섞어 해독할 수 없는 배열을 만듭니다."
-
1단계: 첫 번째 그리드(키 JANAUSTEN)에 일반 텍스트 메시지가 기록됩니다.
-
열은 키에 따라 알파벳 순서로 다음 그리드로 읽힙니다(2단계 참조).
-
2단계: 1단계의 열은 두 번째 그리드(핵심 AEROLANES가 있는)에 기록됩니다.
-
열은 키에 따라 알파벳 순서로 다음 그리드로 읽힙니다(3단계 참조).
-
3단계: 암호문은 종종 5개의 블록(예: RIAES SNELI EEIRP 등)으로 작성됩니다.
색상은 각 전치 단계에서 문자가 어떻게 스크램블되는지 보여줍니다.단일 단계는 약간의 재정렬만 일으키는 반면, 그리드의 마지막 행이 불완전한 경우 두 번째 단계는 상당한 스크램블링 효과를 가져옵니다.
다른 예
예를 들어, 이전 섹션의 불규칙한 기둥 전치 결과를 가져와 다른 키워드인 STRIPE로 두 번째 암호화를 수행할 수 있으며, 이는 순열 "564231"을 제공합니다.
5 6 4 2 3 1 EV LN ADC EREE
이전과 마찬가지로, 이것은 암호문을 제공하기 위해 열 단위로 읽힙니다.
CAEEN SOIAE DRLEF WEDREVETO
길이가 정확히 같은 여러 메시지가 동일한 키를 사용하여 암호화된 경우 동시에 애너그램이 될 수 있습니다.이렇게 하면 메시지 복구와 키 복구가 동시에 발생할 수 있습니다(따라서 해당 키와 함께 전송된 다른 모든 메시지를 읽을 수 있습니다).
제1차 세계 대전 동안 독일군은 이중 기둥 모양의 전치 암호를 사용하여 키를 자주 변경했습니다.이 시스템은 프랑스인들에 의해 정기적으로 해결되었으며, 그들은 보통 며칠밖에 걸리지 않았던 동일한 길이의 메시지를 가로채면 빠르게 열쇠를 찾을 수 있었습니다.그러나, 프랑스의 성공은 널리 알려지게 되었고, Le Matin에서의 출판 이후, 독일인들은 1914년 11월 18일에 새로운 체제로 바뀌었습니다.[3]
제2차 세계 대전 당시 이중 전치 암호는 네덜란드 레지스탕스 단체인 프랑스 마퀴스와 유럽의 지하 활동 관리를 담당하는 영국 특수 작전 집행부(SOE)에 의해 사용되었습니다.[4]미국 전략국[5] 요원들과 독일 육군과 해군의 비상 암호로 사용되기도 했습니다.
VIC 암호가 발명되기 전까지 이중 전치는 일반적으로 에이전트가 어려운 현장 조건에서 안정적으로 작동할 수 있는 가장 복잡한 암호로 여겨졌습니다.
암호 분석
이중 전치 암호는 두 키의 길이의 곱만큼 키를 가진 단일 전치 암호로 취급될 수 있습니다.[6]
2013년 말, 저자에 의해 해독할 수 없는 것으로 간주되는 이중 전치 문제는 조지 래시에 의해 각각의 전치가 개별적으로 공격되는 분할 정복 접근법을 사용하여 해결되었습니다.[7]
미슈코프스키 전치
1902년에 에밀 빅터 테오도르 미슈코프스키가 제안한 변형된 형태의 기둥 전치는 반복되는 글자를 가진 키워드를 필요로 합니다.일반적으로, 키워드 문자의 후속 발생은 알파벳 순서의 다음 문자와 같이 취급됩니다. 예를 들어, 키워드 TOMATO는 "532164"의 숫자 키 문자열을 산출합니다.
Myszkowski 변환에서 반복되는 키워드 문자는 동일하게 번호가 지정되며, TOMATO는 "432143"의 키 문자열을 생성합니다.
4 3 2 1 4 3 WE AREED COVE OF EE
고유한 숫자를 가진 평문 열은 아래쪽으로 전사되고, 반복되는 숫자를 가진 열은 왼쪽에서 오른쪽으로 전사됩니다.
ROFOA CDTED CWEIVE RLENE 참조
전치 장애
붕괴된 전치 암호는[8] 행렬의 행을 불규칙적으로 채우는 것, 즉 일부 공백을 의도적으로 비워두거나(또는 Rasterschlüssel 44에서와 같이 검은색으로) 나중에 평문의 다른 부분 또는 임의의 문자로 채우는 전치 패턴을 더욱 복잡하게 만듭니다.[8]
빗 접근법
이 메서드는 Gen에 속합니다.Luigi Sacco[9])는 평문이 키 번호가 현재 행 번호와 같은 열에 도달하면 새 행을 시작합니다.이것은 불규칙한 행 길이를 만듭니다.예를들면,
FORE EVER JIG SAW < Key 4 8 9 2 12 3 10 7 6 5 11 13 No 후 빈칸:COMP I CAT T * 1 HET R * * * * * * * * * 2 ANS POS * * * * * * * * * * * 3 I * * * * * * * * * * * * * * * * * * * * * * * 5 NL I K E A CO M * * * * 6 B _ _ _ _ _ _ * * * * * 7 *
그런 다음, TPRPN, KISAA, CHAIT, NBERT, EMATO 등의 규칙적인 주상 전치에 따라 기둥을 제거합니다.
수치열 접근법
또 다른 간단한 옵션은[10] 숫자 순서에 따라 빈칸을 배치하는 암호를 사용하는 것입니다.예를 들어, "SECRET"은 "5,2,1,4,3,6"의 시퀀스로 디코딩되어 매트릭스의 5번째 필드를 가로 지운 다음 다시 카운트하고 두 번째 필드를 가로 지웁니다.다음 예는 기둥 키 "CRIPTO"로 기둥 전치를 위해 설정된 행렬로, 중단 키 "SECRET"(별표로 표시)에 따라 교차된 필드로 채워지는 것이며, 남은 공간에 "우리는 발견되었습니다, 즉시 도망칩니다"라는 메시지가 표시됩니다.결과 암호문(변환 키에 따라 읽은 열)은 "WCEEO ERETRIVFC EODN SELEADA"입니다.
14 6 3 5 2 WEAR * E * DIS * CO * VERED * FLE * A * TON * CE *
그릴스
다른 형태의 전치 암호는 그릴이나 잘라낸 부분이 있는 물리적 마스크를 사용합니다.이는 그릴 크기에 따라 지정된 기간 동안 매우 불규칙적으로 변형될 수 있지만, 통신원이 물리적 키를 비밀로 유지해야 합니다.그릴은 1550년에 처음 제안되었고, 제1차 세계대전의 처음 몇 달 동안 여전히 군사적으로 사용되었습니다.
탐지 및 암호 분석
전치는 개별 심볼의 주파수에 영향을 미치지 않기 때문에, 단순 전치는 주파수 카운트를 수행함으로써 암호 분석가에 의해 쉽게 탐지될 수 있습니다.암호문이 평문과 매우 유사한 빈도분포를 나타낸다면, 아마도 전치일 가능성이 높습니다.
일반적으로, 전치 방법은 애너그램(anagramming)에 취약합니다. 암호문 조각을 이리저리 미끄러뜨린 다음 영어로 된 단어나 평문이 쓰인 언어의 애너그램처럼 보이는 섹션을 찾아 애너그램을 해결하는 것입니다.일단 그러한 아날로그들이 발견되면, 그것들은 전치 패턴에 대한 정보를 드러내고, 결과적으로 확장될 수 있습니다.단순한 위치 변경은 키에 매우 가까운 키가 횡설수설로 간간이 나타나는 읽기 쉬운 평문의 긴 섹션을 보여주는 속성으로 인해 종종 어려움을 겪습니다.따라서 이러한 암호는 유전자 알고리즘[11] 및 언덕 오르기 알고리즘과 같은 최적 탐색 알고리즘에 취약할 수 있습니다.[12][13]
전치 암호를 사용하여 인코딩된 메시지를 공격하는 몇 가지 구체적인 방법이 있습니다.여기에는 다음이 포함됩니다.
- 알려진 일반 텍스트 공격:평문의 알려진 부분 또는 추측된 부분(예: 이름, 장소, 날짜, 숫자, 구)을 사용하여 평문의 변환 및/또는 가능한 주제를 수행하는 데 사용되는 가능한 열 순서를 역공학하는 데 도움을 줍니다.
- 무차별 공격:키가 사전 단어 또는 책이나 기타 공개적으로 사용 가능한 소스의 구에서 파생된 경우 수십억 개의 가능한 단어, 단어 조합 및 구를 키로 사용하여 솔루션을 단순화하는 것이 가능할 수 있습니다.
- 깊이 공격:동일한 길이의 두 개 이상의 메시지가 동일한 키로 인코딩된 경우 메시지가 동일한 위치에 의미 있는 텍스트를 표시할 때까지 메시지가 정렬되고 애그램될 수 있습니다.
- 통계적 공격:언어에서 두 글자, 세 글자 등의 조합 빈도에 대한 통계는 어떤 변화가 가장 가능성이 높은 조합을 생성할 것인지에 따라 가능한 위치를 점진적으로 반전시키는 알고리즘에서 채점 함수를 알려주는 데 사용될 수 있습니다.예를 들어, 2글자 쌍 QU는 영어 텍스트에서 QT보다 일반적이므로 암호 분석가는 QU를 함께 배치하는 변환을 시도합니다.
독일 전치 암호의 암호 분석에 대한 자세한 설명은 허버트 야들리의 "미국의 블랙 챔버" 7장에서 찾을 수 있습니다.
조디악 킬러가 사용한 "Z-340"이라고 불리는 암호는 문자에 63개의 다른 기호를 대입한 삼각형 섹션으로 구성되어 있으며, 2020년 12월 5일 국제 민간인 팀이 전문 소프트웨어를 사용하여 해독할 때까지 51년 이상 미해결 상태로 남아 있었습니다.[14]
조합
전치는 종종 평가 방법과 같은 다른 기술과 결합됩니다.예를 들어, 기둥 모양 전치와 결합된 간단한 대체 암호는 둘 다의 약점을 방지합니다.고주파 암호문 기호를 고주파 평문 문자로 대체하면 전치 때문에 평문 덩어리가 나타나지 않습니다.치환 때문에 전치를 애너그램하는 것은 작동하지 않습니다.이 기법은 분획법과 결합하면 특히 강력합니다(아래 참조).단점은 이러한 암호들이 단순한 암호들보다 상당히 더 힘들고 오류가 날 수 있다는 것입니다.
분획법
전치(transposition)는 분할(precation)과 함께 사용될 때 특히 효과적입니다. 즉, 각 평문 기호를 두 개 이상의 암호문 기호로 나누는 예비 단계입니다.예를 들어, 일반 텍스트 알파벳은 격자 형태로 작성될 수 있으며, 메시지의 모든 글자는 좌표로 대체됩니다(폴리비우스 정사각형 및 스트래들링 바둑판 참조).[15]분할의 또 다른 방법은 점과 대시뿐만 아니라 공백을 나타내는 기호를 사용하여 메시지를 모스 부호로 간단히 변환하는 것입니다.[16]
그러한 분류된 메시지가 전치되면 개별 문자의 구성 요소가 메시지에서 광범위하게 분리되어 클로드 E를 달성합니다. 섀넌의 확산.분할과 전치를 결합한 암호의 예로는 이중 암호, 삼중 암호, ADFGVX 암호, VIC 암호 등이 있습니다.
또 다른 선택은 각 문자를 이진 표현으로 바꾸고, 이를 바꿔 새로운 이진 문자열을 해당하는 ASCII 문자로 변환하는 것입니다.이진 문자열을 ASCII 문자로 변경하기 전에 스크램블링 프로세스를 여러 번 반복하면 깨지기가 더 어려워질 수 있습니다.많은 현대 블록 암호들은 이 단순한 아이디어와 관련된 더 복잡한 형태의 전치를 사용합니다.
참고 항목
메모들
- ^ Elonka, Dunin; Schmeh, Klaus (2020). Codebreaking: A Practical Guide. Robinson. p. 247. ISBN 978-1-4721-4421-8. OCLC 1158165142.
- ^ Smith, Laurence Dwight (1955) [1943], Cryptography / The Science of Secret Writing, New York: Dover, pp. 16, 92–93
- ^ 칸, 301-304쪽.
- ^ 칸, 535쪽과 539쪽.
- ^ 칸, 539쪽.
- ^ Barker, Wayne (1995). Cryptanalysis of the Double Transposition Cipher: Includes Problems and Computer Programs. Aegean Park Press.
- ^ Lasry, George (2014-06-13). "Solving the Double Transposition Challenge with a Divide-and-Conquer Approach". Cryptologia. 38 (3): 197–214. doi:10.1080/01611194.2014.915269. S2CID 7946904.
- ^ a b Mahalakshmi, B. (June 2016). "An Overview on Disrupted Transposition Cipher for Security Enhancement" (PDF). International Journal of Computer Applications. 143 (13): 9–12. doi:10.5120/ijca2016910308. Archived (PDF) from the original on 2018-06-04. Retrieved 7 January 2021.
- ^ Savard, John. "Methods of Transposition". A Cryptographic Compendium. Retrieved 27 June 2023.
- ^ jdege (11 November 2014). "A simple disrupted transposition". Retrieved 7 January 2021.
- ^ Matthews, Robert A. J. (April 1993). "The Use of Genetic Algorithms in Cryptanalysis". Cryptologia. 17 (2): 187–201. doi:10.1080/0161-119391867863.
- ^ Lasry, George; Kopal, Nils; Wacker, Arno (2014-07-03). "Solving the Double Transposition Challenge with a Divide-and-Conquer Approach". Cryptologia. 38 (3): 197–214. doi:10.1080/01611194.2014.915269. ISSN 0161-1194. S2CID 7946904.
- ^ Lasry, George; Kopal, Nils; Wacker, Arno (2016-07-03). "Cryptanalysis of columnar transposition cipher with long keys". Cryptologia. 40 (4): 374–398. doi:10.1080/01611194.2015.1087074. ISSN 0161-1194. S2CID 21179886.
- ^ "Zodiac Killer cipher is cracked after eluding sleuths for 51 years". arstechnica.com. 2020-12-12. Retrieved 2020-12-12.
- ^ 다니엘 로드리게스 클랙."분획 암호문을 변환하는 중."
- ^ 제임스 라이온스.'분절 모스 암호'
참고문헌
- 칸, 데이빗.코드브레이커:비밀스런 글쓰기 이야기.서브 목사님.스크라이브너, 1996년
- 야들리, 허버트.아메리칸 블랙 체임버.밥스-메릴, 1931년