{"id":1821,"date":"2015-02-02T10:12:36","date_gmt":"2015-02-02T10:12:36","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=1821"},"modified":"2015-02-02T10:28:02","modified_gmt":"2015-02-02T10:28:02","slug":"solving-the-2014-apl-problem-solving-competition-cryptography-problem-3","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2015\/02\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-3\/","title":{"rendered":"Solving the 2014 APL Problem Solving Competition \u2013 Cryptography Problem 3"},"content":{"rendered":"<p>This post is the continuation of the series where we examine some of the problems selected for the 2014 <a href=\"http:\/\/www.dyalogaplcompetition.com\/\" target=\"_blank\">APL Problem Solving Competition<\/a>. In this post we&#8217;ll conclude looking at the cryptography problems from <a href=\"http:\/\/www.dyalog.com\/uploads\/files\/student_competition\/2014_problems_phase2.pdf\" target=\"_blank\">Phase II<\/a> that we started looking at in a <a title=\"Solving the 2014 APL Problem Solving Competition \u2013 Cryptography Problem 1\" href=\"http:\/\/www.dyalog.com\/blog\/2015\/01\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-1\/\" target=\"_blank\">previous blog post<\/a> and continued in a <a title=\"Solving the 2014 APL Problem Solving Competition \u2013 Cryptography Problem 2\" href=\"http:\/\/www.dyalog.com\/blog\/2015\/01\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-2\/\" target=\"_blank\">further blog post<\/a>.<\/p>\n<h2>Cryptography Problem 3 \u2013 Playfair Cipher<\/h2>\n<p><strong><em>Task 1 \u2013 Squaring Off<\/em><\/strong><\/p>\n<p>The first task is to convert a string into a 5\u00d75 Playfair table. The solution makes straightforward use of APL primitives:<\/p>\n<ul>\n<li>Unique (<code class=\"language-apl\">\u222a<\/code>) to remove duplicate characters from the string.<\/li>\n<li>Without (<code class=\"language-apl\">~<\/code>) to find the rest of the alphabetic characters that are not mentioned in the string, and again to remove the character J.<\/li>\n<\/ul>\n<pre><code class=\"language-apl\">PlayfairTable\u2190{\r\n    k\u2190\u222a\u2375\r\n    5 5\u2374(k,\u2395A~k)~'J'\r\n}<\/code><\/pre>\n<p>Here it is in action:<\/p>\n<pre><code class=\"language-apl\">      \u22a2table\u2190PlayfairTable'KENNETHEIVERSON'\r\nKENTH\r\nIVRSO\r\nABCDF\r\nGLMPQ\r\nUWXYZ<\/code><\/pre>\n<p><strong><em>Task 2 \u2013 Encryption<\/em><\/strong><\/p>\n<p>To encrypt a message we need to take two characters at a time, find their coordinates in the 5\u00d75 Playfair table, swap their column coordinates and look up the letters at the new coordinates. There are lots of tricks in the code below of which we&#8217;ll describe just a few:<\/p>\n<ul>\n<li>To process the message two characters at a time, appending to the result as we go, we use a tail-recursive dfn whose left argument accumulates the result. For an introduction to this technique see this implementation of <a href=\"http:\/\/dfns.dyalog.com\/n_fibonacci.htm\" target=\"_blank\">the Fibonacci function<\/a>.<\/li>\n<li>To find letters in the Playfair table we first look them up in the ravel (i.e. the linearised form) of the table, and then use Encode (<code class=\"language-apl\">\u22a4<\/code>) to convert this linear index into a pair of coordinates. Decode (<code class=\"language-apl\">\u22a5<\/code>) does the opposite, converting a pair of coordinates back into a linear index.<\/li>\n<li>Mix (<code class=\"language-apl\">\u2191<\/code>) and Split (<code class=\"language-apl\">\u2193<\/code>) are used to convert between two different representations of the coordinates of the two characters we&#8217;re encoding: either as a flat 2\u00d72 matrix, or as a nested 2-vector of 2-vectors. The choice of representation is largely a matter of taste, and it might be fun to play with this part of the code. You could tweak it to work entirely with the flat representation, or entirely with the nested representation, rather than converting back and forth between them.<\/li>\n<\/ul>\n<pre><code class=\"language-apl\">PlayfairEncrypt\u2190{\r\n    \u2395IO\u21900                       \u235d To aid arithmetic modulo 5.\r\n    t\u2190\u237a                         \u235d The Playfair table.\r\n    m\u2190\u2375,(2|\u2262\u2375)\/'Z'              \u235d Add a Z if the message length is odd.\r\n    ((m='J')\/m)\u2190'I'             \u235d Convert J to I in the message.\r\n    ''{                         \u235d Start with an empty accumulator.\r\n        0=\u2262\u2375:\u237a                  \u235d Finished: return the accumulated encrypt.\r\n        1=\u2262\u2375:\u237a \u2207 \u2375,'X'          \u235d Only one character left: add an X.\r\n        p\u21902\u2191\u2375\r\n        =\/p:\u237a \u2207(\u2283\u2375),'X',1\u2193\u2375     \u235d Duplicate character: insert an X.\r\n        c\u2190(\u2374t)\u22a4(,t)\u2373p           \u235d Coords of each letter in the table.\r\n        c\u2190{\r\n            =\/1\u2191\u2375:\u2191(\u2374t)|0 1+\u2193\u2375  \u235d Same row: move to the right.\r\n            =\/1\u2193\u2375:\u2191(\u2374t)|1 0+\u2193\u2375  \u235d Same column: move down.\r\n            0 1\u233d\u2375               \u235d Else swap column coords.\r\n        }c\r\n        p\u2190(,t)[(\u2374t)\u22a5c]          \u235d Look up new coords in table.\r\n        (\u237a,p)\u2207 2\u2193\u2375              \u235d Tail recursion.\r\n    }m\r\n}<\/code><\/pre>\n<p>Here it is in action:<\/p>\n<pre><code class=\"language-apl\">      \u22a2cipher\u2190table PlayfairEncrypt'HELLOWORLD'\r\nKNMWQVZVVMCY<\/code><\/pre>\n<p>(Note that this result is slightly different from that given in the <a href=\"http:\/\/www.dyalog.com\/uploads\/files\/student_competition\/2014_problems_phase2.pdf\" target=\"_blank\">original problem description<\/a>, because of some confusion about the rules for handling duplicate letters and odd message lengths, which were clarified later in the student competition forums.)<\/p>\n<p><strong><em>Task 3 \u2013 Decryption<\/em><\/strong><\/p>\n<p>Decryption is very similar to encryption. The differences are:<\/p>\n<ul>\n<li>Letters found in the same row of the table need to move left instead of right, and letters in the same column need to move up instead of down.<\/li>\n<li>We don&#8217;t need to worry about the input having an odd length, or containing the letter J.<\/li>\n<\/ul>\n<p>Hence the code for <code class=\"language-apl\">PlayfairDecrypt<\/code> is shorter than but very similar to <code class=\"language-apl\">PlayfairEncrypt<\/code>:<\/p>\n<pre><code class=\"language-apl\">PlayfairDecrypt\u2190{\r\n    \u2395IO\u21900                       \u235d To aid arithmetic modulo 5.\r\n    t\u2190\u237a                         \u235d The Playfair table.\r\n    ''{                         \u235d Start with an empty accumulator.\r\n        0=\u2262\u2375:\u237a                  \u235d Finished: return the accumulated encrypt.\r\n        p\u21902\u2191\u2375\r\n        c\u2190(\u2374t)\u22a4(,t)\u2373p           \u235d Coords of each letter in the table.\r\n        c\u2190{\r\n            =\/1\u2191\u2375:\u2191(\u2374t)|0 \u00af1+\u2193\u2375 \u235d Same row: move to the left.\r\n            =\/1\u2193\u2375:\u2191(\u2374t)|\u00af1 0+\u2193\u2375 \u235d Same column: move up.\r\n            0 1\u233d\u2375               \u235d Else swap column coords.\r\n        }c\r\n        p\u2190(,t)[(\u2374t)\u22a5c]          \u235d Look up new coords in table.\r\n        (\u237a,p)\u2207 2\u2193\u2375              \u235d Tail recursion.\r\n    }\u2375\r\n}<\/code><\/pre>\n<p>Here it is in action:<\/p>\n<pre><code class=\"language-apl\">      table PlayfairDecrypt cipher\r\nHELXLOWORLDX<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we&#8217;ll conclude looking at the cryptography problems from Phase II that we started looking &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2015\/02\/solving-the-2014-apl-problem-solving-competition-cryptography-problem-3\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":15,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,8,22],"tags":[],"class_list":["post-1821","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-apl-language","category-student-competition"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1821","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=1821"}],"version-history":[{"count":24,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1821\/revisions"}],"predecessor-version":[{"id":2076,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1821\/revisions\/2076"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=1821"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=1821"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=1821"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}