Lottery를 이용한 단일 대치 암호문 해독

운영체제를 공부하다 보면 여러가지의 스케줄링 기법을 배울 수 있다.

그 중 재밌는 스케줄링이 존재한다. 

Lottery 스케줄링 : 우선순위 스케줄링의 경우 기아상태가 발생할 수 있다. 낮은 순위의 프로세스는 한없이 대기상태로 남아 있을 수 있기 때문이다. 이러한 단점을 극복하기 위해 새롭게 제안된 스케줄링이다. 이는 각 프로세스에게 복권을 주고 무작위로 선택하여 스케줄링한다. 단 우선순위가 높은 스케줄링에게 복권을 차등 지급하면 아무래도 우선순위가 높은 프로세스는 더 많은 CPU 사용기회를 얻을 수 있다.

이 기법을 이용해 단일 대치 암호문을 해독해보겠다.

1. 소개

알파벳 빈도 분포, 추론, 가정 등을 통해 암호문을 해독한다. 암호문은 다음과 같다. 

vkzqidawkdiezvqzebsjvbxqzbhsjvnsqbhsdjmdqmdqzjvsavaszjazsjishzqbhpqzzvnzasbiitmdqhkzrbtksvbaphzvhpltdmbaqsezvazjztszilvvebiiaipzvbvhdhkznqzasvzvzcpzjazdmzuzjhvkzebwzvxqzbhpvzdmhqbazzuslzjazvpakbvvkdzbjlhsqzsenqzvvsdjvbvrziibvmsjxzqnqsjhvfbiisvhsavbjlkbjlrqshsjxbjbitvsvjdrwjdrjbvcpzvhsdjzlldapezjhzybesjbhsdjvpakzuslzjazsvpvzlhdhzvhhkzdqszvadjazsuzlfthkzndisazmdqzybenizdqfthkzsjuzvhsxbhdqksevzimbiidmhkzhzakjscpzvbludabhzlftkdiezvibhzqfzabezqzbishtfphrzqzxzjzqbiitsjhkzsqsjmbjatbhhkzhsezadjbjldtizrbvrqshsjxsjebjtdmksvqzndqhzlabvzvkdiezvmqzcpzjhitadenibsjvdmhkzrbthkzaqsezvazjzkbvfzzjadjhbesjbhzlftdhkzqvzvnzasbiitfthkzndisazzenkbvsvsjxhkzaqshsabisendqhbjazdmebsjhbsjsjxshvsjhzxqshtbjdrrziiwjdrjmzbhpqzdmaqsezvazjzzybesjbhsdjdrsjxhdhkzvebiivabizdmhkzhqbazzuslzjazvpakbvhdfbaadbvkkbsqdqmsjxzqnqsjhvkzdmhzjpvzvbebxjsmtsjxxibvvbhhkzvazjzbjlbjdnhsabiesaqdvadnzfbawbhksvidlxsjxvsjfbwzqvhqzzhkzpvzvbjbithsabiakzesvhqtmdqfiddlqzvslpzbjbitvsvbvrziibvhdysadidxtzybesjbhsdjbjllzhzqesjbhsdjmdqndsvdjvkdiezvvzzevhdkbuzebsjhbsjzlbvebiiakzesvhqtibfdqbhdqtsjksvidlxsjxvnqzvpebfitpvsjxvsenizrzhakzesabiezhkdlvmdqlzhzahsdjdmvnzasmsahdysjvmdqzybenizhkzbluzjhpqzdmhkzjbubihqzbhtfbiisvhsavsvpvzlrkzjvnzjhfpiizhvabjfzqzaduzqzlbjlhkzsqabisfqzezbvpqzlbjlebhakzlrshkbvpvnzahzlepqlzqrzbndjbvsjhkzbluzjhpqzdmhkzzenhtkdpvzkdiezvrbvbivduzqtnzqaznhsuzdmhkzlqzvvbjlbhhshplzdmksvaiszjhvbjlvpvnzahvjdhsjxvhtizbjlvhbhzdmrzbqdmhkzsqaidhkzvbjtadjhbesjbhsdjvpakbvaibtdjfddhvhkzsqvhbhzdmesjlbjlnktvsabiadjlshsdjsjdqlzqhdsjmzqhkzsqdqsxsjbjlqzazjhksvhdqtvwsjebqwvvpakbvhbhhddvadpilqzuzbiepakbfdphhkzsqksvhdqtkzbnniszlhkzvbezezhkdlhdnzqvdjbishzevvpakbvrbiwsjxvhsawvmbedpvitsjhkzkdpjldmhkzfbvwzqusiizvdqkbhvsjhkzabvzdmhkzfipzabqfpjaizrshkvebiilzhbsivvpakbvezlbiisdjvrzbqbjladjhbesjbhsdjtszilsjxushbisjlsabhdqvdmhkzsqbfvzjhdrjzqv

각 암호문을 해독하기 위해서는 알파벳 빈도수를 이용해야 한다.

따라서 위 그림과 같은 빈도수를 이용해 암호를 해독해야만 한다. 하지만 문장이 길지 않을 경우 이러한 빈도수는 정확하게 대칭되지 않는다. 따라서 어느 정도의 오차를 해결해야한다. 따라서 그 오차를 해결하기 위해 CPU 스케줄링 방식 중 복권 스케줄링 방식을 응용해 이 문제를 해결했다. 이 방식을 이용할 경우 오차문제를 해결할 수 있으면서 암호문의 빈도수 공격을 가능하게 했다. 하지만 자주 쓰이면서 오차 범위가 넓은 L, C, U, M, W의 5개의 알파벳은 추론과 가정을 통해 해독해야만 했다. 

2. 과정

각 과정은 다음과 같다.

1차 단계 : 암호문 알파벳의 빈도 랭킹 만큼 복권을 지급

각 암호문의 알파벳 빈도수를 측정하고 빈도수를 이용해 정렬한다. 그리고 순서대로 복권을 지급한다. 즉 빈도수가 가장 높은 알파벳에겐 26개의 복권을 지급하고 가장 빈도수가 낮은 알파벳에겐 0개의 복권을 지급한다.

2차 단계 : 복권 당첨

각 복권은 0부터 25원까지의 금액이 당첨된다. 만약 운이 없을 경우 각 알파벳의 빈도 순위는 바뀔 수가 있다. 즉 26개의 복권을 가지고 있더라도 랜덤한 확률로 모두 0원만 당첨될 경우 가지고 있는 금액은 0원이 될 수 있다. 하지만 보통 많은 복권을 가지고 있다면 많은 금액이 당첨될 수 있다. 복권을 모두 당첨한 뒤 총금액을 이용해 다시 정렬한다. 정렬된 순서대로 그 후 그림 1과 같은 일반적인 알파벳 빈도수를 이용해 각 알파벳을 대칭시킨다. 암호문을 새롭게 구한 빈도수로 이용해 해독한다.

3차 단계 : Diagram 이용

하지만 2차 단계까지의 복권 당첨 방식은 정확하지가 않다. 좀 더 정답에 근접한 해독을 위해 Dragram을 이용한다. 이용할 Diagram은 다음과 같다. 

The, Ing, End, Es, Of, Er 이다. 이와 같은 Diagram을 이용한 이유는 자주 나오는 diagram 이면서 6개의 Diagram을 이용해 D, E, F, G, H, I, N, O, R, T 10개의 정확한 알파벳 대칭 값을 알 수 있기 때문이다. 각 Diagram 은 모두 10개 이상일 때만 출력시켰다. 

3. 결론

위의 알고리즘을 통해 약 20분 동안 아래와 같은 대칭 결과를 얻을 수 있었다. 1차단계와 2차단계를 통한 결과가 표 2와 같다.

a(85)   (1차단계 : 복권추첨)->>   a(159)  (2차단계 : 정렬 및 대칭)->>   l b(152) (1차단계 : 복권추첨)->>   b(290) (2차단계 : 정렬 및 대칭)->>   a c(4) (1차단계 : 복권추첨)->>   c(6)    (2차단계 : 정렬 및 대칭)->>   x d(120) (1차단계 : 복권추첨)->>   d(244) (2차단계 : 정렬 및 대칭)->>   o e(55) (1차단계 : 복권추첨)->>   e(157) (2차단계 : 정렬 및 대칭)->>   c f(25) (1차단계 : 복권추첨)->>   f(100) (2차단계 : 정렬 및 대칭)->>   p g(0) (1차단계 : 복권추첨)->>   g(24)  (2차단계 : 정렬 및 대칭)->>   q h(147) (1차단계 : 복권추첨)->>   h(292) (2차단계 : 정렬 및 대칭)->>   t i(86) (1차단계 : 복권추첨)->>   i(154) (2차단계 : 정렬 및 대칭)->>   u j(129) (1차단계 : 복권추첨)->>   j(218) (2차단계 : 정렬 및 대칭)->>   n k(80) (1차단계 : 복권추첨)->>   k(185) (2차단계 : 정렬 및 대칭)->>   h l(56) (1차단계 : 복권추첨)->>   l(177) (2차단계 : 정렬 및 대칭)->>   d m(39) (1차단계 : 복권추첨)->>   m(128) (2차단계 : 정렬 및 대칭)->>   f n(32)   (1차단계 : 복권추첨)->>   n(102) (2차단계 : 정렬 및 대칭)->>   y o(0) (1차단계 : 복권추첨)->>   o(0)  (2차단계 : 정렬 및 대칭)->>   z p(42) (1차단계 : 복권추첨)->>   p(149) (2차단계 : 정렬 및 대칭)->>   m q(92)   (1차단계 : 복권추첨)->>   q(179) (2차단계 : 정렬 및 대칭)->>   r r(24) (1차단계 : 복권추첨)->>   r(76)    (2차단계 : 정렬 및 대칭)->>   b s(146) (1차단계 : 복권추첨)->>   s(228) (2차단계 : 정렬 및 대칭)->>   i t(38) (1차단계 : 복권추첨)->>   t(132) (2차단계 : 정렬 및 대칭)->>   w u(17) (1차단계 : 복권추첨)->>   u(73)  (2차단계 : 정렬 및 대칭)->>   v v(151) (1차단계 : 복권추첨)->>   v(206) (2차단계 : 정렬 및 대칭)->>   s w(11) (1차단계 : 복권추첨)->>   w(44)  (2차단계 : 정렬 및 대칭)->>   k x(25)   (1차단계 : 복권추첨)->>   x(121) (2차단계 : 정렬 및 대칭)->>   g y(7)   (1차단계 : 복권추첨)->>   y(33)    (2차단계 : 정렬 및 대칭)->>   j z(225) (1차단계 : 복권추첨)->>   z(329) (2차단계 : 정렬 및 대칭)->>   e

그 후 3차단계를 진행했다. 

the 개수 : 34, ing 개수 : 14, and 개수 : 14, es 개수 : 33, of 개수 : 21, er 개수 : 21

그 결과 다음과 같이 암호문이 해독되었다.

sheruolkhoucesrecainsagreatinsyirationforforensilslienleinuiteratmreesyeliauuwforthebawhisalmtestmdwofalriceslenewieudsscauulumesastotheyrelisesexmenleofeventshecakesgreatmseoftraleevidenlesmlhasshoeandtireicyressionsasbeuuasfingeryrintspauuistilsandhandbritinganauwsisnobknobnasxmestioneddolmcentejacinationsmlhevidenleismsedtotesttheorieslonleivedpwtheyouileforejacyueorpwtheinvestigatorhicseufauuofthetelhnixmesadvolatedpwhoucesuaterpelacereauitwpmtberegenerauuwintheirinfanlwattheticelonandowuebasbritingincanwofhisreyortedlaseshoucesfrexmentuwlocyuainsofthebawthelriceslenehaspeenlontacinatedpwothersesyeliauuwpwtheyouileecyhasisingthelritilauicyortanleofcaintainingitsintegritwanobbeuuknobnfeatmreoflricesleneejacinationobingtothescauuslaueofthetraleevidenlesmlhastopalloashhairorfingeryrintsheoftenmsesacagnifwingguassatthesleneandanoytilaucilrosloyepalkathisuodgingsinpakerstreethemsesanauwtilaulhecistrwforpuoodresidmeanauwsisasbeuuastojilouogwejacinationanddetercinationforyoisonshoucesseecstohavecaintainedascauulhecistrwuaporatorwinhisuodgingsyresmcapuwmsingsicyuebetlhecilaucethodsfordeteltionofsyelifiltojinsforejacyuetheadventmreofthenavautreatwpauuistilsismsedbhensyentpmuuetslanpereloveredandtheirlauipreceasmredandcatlhedbithasmsyeltedcmrderbeayonasintheadventmreoftheecytwhomsehoucesbasausoverwyerleytiveofthedressandattitmdeofhisluientsandsmsyeltsnotingstwueandstateofbearoftheirluothesanwlontacinationsmlhasluawonpootstheirstateofcindandyhwsilaulonditioninordertoinfertheiroriginandrelenthistorwskincarkssmlhastattooslomudreveaucmlhapomttheirhistorwheayyuiedthesacecethodtoyersonauitecssmlhasbaukingstilksfacomsuwinthehomndofthepaskerviuuesorhatsinthelaseofthepumelarpmnluebithscauudetaiussmlhascedauuionsbearandlontacinationwieudingvitauindilatorsoftheirapsentobners

하지만 이 암호문은 정확하지 않았고 추론과 가정을 통해 L, C, U, M, W의 5개의 알파벳을 해독해야만 했다. forensic이라는 단어를 이용해 c알파벳을 알 수 있었고 remains 이란 단어를 통해 m알파벳을 알 수 있었다. acute 라는 단어를 통해 U를 알 수 있었고 그 다음으로 자주 나오는 단어 2글자에 L과 W를 대입했다. 그 결과 80퍼센트에 가까운 해독결과를 얻을 수 있었다.  그 이 후 나머지 알파벳을 해독했고 다음과 같은 결과를 얻을 수 있었다.

Sherlock Holmes remains a great inspiration for forensic science, inliterature especially for the way his acute study of a crime scene yields small clues as to the precise sequence of events. He makes great use of trace evidence such as shoe and tire impressions, as well as fingerprints, ballistics and handwriting analysis, now known as questioned document examination. Such evidence is used to test theories conceived by the police, for example, or by the investigator himself. All of the techniques advocated by Holmes later became reality, but were generally in their infancy at the time Conan Doyle was writing.  In many of his reported cases, Holmes frequently complains of the way the crime scene has been contaminated by others, especially by the police, emphasising the critical importance of maintaining its integrity, a now well-known feature of crime scene examination. Owing to the small scale of the trace evidence (such as tobacco ash, hair or fingerprints), he often uses a magnifying glass at the scene, and an optical microscope back at his lodgings in Baker Street. He uses analytical chemistry for blood residue analysis as well as toxicology examination and determination for poisons. Holmes seems to have maintained a small chemistry laboratory in his lodgings, presumably using simple wet chemical methods for detection of specific toxins, for example. The adventure of the naval treaty Ballistics is used when spent bullets can be recovered, and their calibre measured and matched with a suspect murder weapon as in the adventure of the empty house. Holmes was also very perceptive of the dress and attitude of his clients and suspects, noting style and state of wear of their clothes, any contamination (such as clay on boots), their state of mind and physical condition in order to infer their origin and recent history.  Skin marks such as tattoos could reveal much about their history. He applied the same method to personal items such as walking sticks (famously in "The Hound of the Baskervilles") or hats (in the case of "The Blue Carbuncle"), with small details such as medallions, wear and contamination yielding vital indicators of their absent owners.

이 때 사용한 코드는 다음과 같다 C++을 이용해 개발하였다.

frequencyAnalysis.zip