솔리테어(주변)

Solitaire (cipher)

솔리테어 암호 알고리즘은 닐 스티븐슨의 의뢰로 닐 슈나이어가 자신의 소설 크립토노미콘에 사용하기 위해 고안한 것으로, 필드 요원들이 전자제품에 의존하거나 유죄를 입증하는 도구를 휴대할 필요 없이 안전하게 통신하기 위해 이 알고리즘을 사용한다.[1]그것은 일반적인 카드놀이로 계산된 수동 암호체계로 설계되었다.크립토노미콘에서 이 알고리즘은 원래 카드놀이에 관련된 사실을 감추기 위해 폰티펙스라고 불렸다.

솔리테어 창조의 동기 중 하나는 전체주의 환경에서, 일련의 암호 유틸리티를 가진 개인용 컴퓨터보다 카드 한 벌의 가격이 훨씬 더 저렴하다는 것이다.그러나 슈나이어가 크립토노미콘의 부록에서 경고하듯이, 암호 분석에 관심이 있는 거의 모든 사람들이 이제 이 알고리즘에 대해 알게 될 것이기 때문에, 카드 한 장을 들고 다니는 것 또한 유죄판결을 받는 것으로 간주될 수 있다.더욱이, 분석 결과, 암호의 결함이 발견되어 현재는 안전하지 않은 것으로 간주되고 있다.

암호화 및 암호 해독

이 알고리즘은 A조커와 B조커라고 불리는 52개의 적합한 카드와 2개의 조커가 있는 표준 카드 데크를 사용한다.간단히 말해서, 이 예에서는 클럽과 다이아몬드 두 벌만 사용될 것이다.각 카드에는 숫자 값이 할당된다. 클럽의 번호는 1부터 13까지(에이스에서 킹까지), 다이아몬드는 14부터 26까지 같은 방식으로 매겨진다.조커에게는 27과 28의 값이 할당될 것이다.따라서 클럽의 잭은 11의 값을 가지며, 다이아몬드의 두 개는 15의 값을 갖게 된다.(카드의 전체 갑판에서 양복은 클럽, 다이아몬드, 하트, 스페이드 등 브리지 순서로 평가되며, 적합한 카드는 1부터 52까지, 조커는 53과 54까지이다.)

암호화 또는 암호 해독을 시작하려면 이전에 동의한 순서대로 카드 데크를 위로 정렬하십시오.메시지의 암호를 해독하는 사람은 메시지를 암호화한 사람이 사용하는 데크와 같은 순서로 데크를 배열해야 한다.처음에 순서를 결정하는 방법은 받는 사람에게 달려있다. 다른 많은 방법들이 있지만, 완벽하게 무작위로 갑판을 흔드는 것이 바람직하다.

알고리즘은 키스트림을 생성하는데, 키스트림은 이를 암호화하고 해독하기 위한 메시지와 결합된다.키스트림의 각 값은 메시지의 한 문자를 암호화하는 데 사용되므로 키스트림은 최소한 메시지만큼 길어야 한다.키스트림이 메시지보다 길면 메시지가 추가 반복 문자로 패딩되어 공격자가 메시지의 정확한 길이를 알지 못하게 할 수 있다.

메시지를 암호화하려면:

  1. A~Z 26자만 남기고 모든 문장 부호와 공백을 제거한다.
  2. 각 문자를 자연 숫자 값 A = 1, B = 2, ..., Z = 26으로 변환한다.
  3. 아래 키스트림 알고리즘을 사용하여 메시지의 각 문자에 대해 하나의 키스트림 값을 생성하십시오.
  4. 각 키스트림 값을 해당 일반 텍스트 숫자에 추가하여 결과 값이 26보다 클 경우 26을 뺀다.(수학에서는 이것을 모듈식 산술이라고 한다.)
  5. 결과 숫자를 다시 문자로 변환하십시오.이 글자의 순서는 암호문이다.

암호문을 해독하려면:

  1. 암호문의 각 문자를 자연 숫자 값으로 변환한다.
  2. 암호 텍스트의 각 문자에 대해 하나의 키 스트림 값을 생성하십시오.
  3. 각 키 스트림 값을 해당 암호 텍스트 값에서 빼내고 결과 값이 1보다 작을 경우 26을 추가하십시오.
  4. 결과 숫자를 다시 문자로 변환하십시오.

키스트림 알고리즘

이 알고리즘은 데크 안에서 카드를 움직여서 키스트림 값을 생성한다.키스트림 알고리즘은 결정론적이므로 키스트림 값은 데크의 초기 순서에 따라서만 달라진다.데크는 원형 배열로 가정되는데, 이는 카드를 데크의 하단 카드 아래로 이동시킬 필요가 있을 경우 카드를 다시 위로 회전시키기만 한다는 것을 의미한다(즉, 첫 번째 카드는 마지막 카드를 따른다).이 시작 데크를 예로 들어보자.

  • 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26

다음 단계를 수행하여 키 스트림의 문자 하나를 생성하십시오.

  1. A 조커(값 27)를 찾아 데크 아래로 한 위치씩 이동시킨다.마지막 카드라면 두 번째 카드가 된다.그것이 첫 번째 카드가 될 방법은 없다.이제 갑판은 다음과 같다.
    • 1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
  2. B 조커(값 28)를 찾아 데크 아래로 2개씩 이동시킨다.마지막 카드의 두 번째 카드일 경우, 두 번째 카드를 싸서 두 번째 카드가 된다는 점에 유의하십시오.마지막 카드라면 세 번째 카드가 된다.그것이 첫 번째 카드가 될 방법은 없다.
    • 1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
  3. "트리플 컷"을 수행하십시오. 데크를 세 부분으로 나누십시오.상단 조커 위의 모든 것(몇 번 반복한 후에 반드시 A조커가 아닐 수도 있음)과 하단 조커 아래의 모든 것이 교환될 것이다.조커들 자신들, 그리고 그들 사이의 카드는 손대지 않은 채로 남아 있다.
    • 5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 6
  4. "카운트 컷"을 수행하십시오. 데크 하단에 있는 카드의 값을 확인하십시오.만약 카드가 조커라면, 그 값을 27로 가져간다.그 수의 카드를 데크 상단에서 제거한 후 데크의 마지막 카드 바로 위에 삽입하십시오.
    • 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
  5. 자, 톱카드의 가치를 보십시오.다시 말하지만, 어느 쪽 조커도 27로 계산된다.그 카드 아래의 이 많은 곳을 세고 그 카드의 값을 키스트림의 다음 값으로 삼으십시오.카운트된 카드가 조커일 경우 이를 무시하고 키스트림 알고리즘을 반복하십시오.이 예에서 상단 카드는 23이므로 24번째 카드인 11까지 계산한다. 따라서 키스트림 값은 11이다. (이 단계에서 어떤 카드도 위치를 변경하지 않으며, 이 단계는 단순히 키스트림 값을 결정한다.)

암호해석

1999년에 Paul Crowley는 예상된 1/26 문자보다 1/22.5 문자마다 발생하는 키스트림에서 반복되는 문자에 대한 편견이 있다는 것을 발견했다.[2]그 결과, 솔리타이어는 문자당 약 0.0005비트의 속도로 정보를 누설한다.[3]그것의 보안은 아마도 매우 짧은 메세지에 적합할지 모르지만, 일반적으로 솔리타이어는 불안정한 것으로 여겨진다.

Crowley는 또한 경우에 따라 키스트림 알고리즘을 실행한 후 동일한 구성이 되는 두 개의 다른 데크 구성이 있다는 것을 알아챘다.예를 들어, A 조커가 갑판 하단 또는 갑판 상단에 있을 경우, 1단계 이후 두 번째 카드가 된다.이것은 슈나이어가 원래 주장했던 것처럼 알고리즘이 항상 되돌릴 수 있는 것은 아니라는 것을 의미한다.[2]

2019년 다니엘 슈는 사용자가 수작업으로 구현하는 것을 더욱 어렵게 하는 비용으로 보안을 높이는 알고리즘의 수정을 제안했다.[3]

참조

  1. ^ Schneier, Bruce (May 1999). "Solitaire". Retrieved 2 July 2006.
  2. ^ a b Crowley, Paul. "Problems with Bruce Schneier's "Solitaire"". Retrieved 26 March 2018.
  3. ^ a b Shiu, Daniel (13 Sep 2019). "Analysis of Solitaire". arXiv:1909.06300 [cs.CR].

외부 링크