So, last time, we looked at simple substitution ciphers. In a substitution
\ncipher, you take each letter, and pick a replacement for it. To encrypt a
\nmessage, you just substitute the replacement for each instance of each letter.
\nAs I explained, it’s typically pretty each to break that encryption – the basic
\nsecret of the encryption is the substitution system, and it’s pretty easy to
\nfigure that out, because the underlying information being encrypted still has a
\nlot of structure. <\/p>\n
There are a couple of easy improvements on a simple substitution cipher, some of which came up in the comments. For example, two
\ngood easy improvements are:<\/p>\n
Both of those changes help. They work particularly well when combined. To do
\na two-character version of that, you create a list of all possible two-character
\nsequences. Then you generate a frequency table for how often each two-character
\nsequence occurs in a large sample of the kind of text you’re going to encode.
\nThen, finally, you assign a number of substitutions for each pair so that they
\noccur with approximately equal frequency. That gives you a pretty good
\nsystem.<\/p>\n
Still, it’s not great. Given enough encoded text, it can be cracked with a
\nrelatively small amount of computational power. If I know the basic idea of the
\ncipher, and I’ve got a decent amount of encoded text, I can write a program that
\nwill figure it out pretty quickly. Plus, it’s really a lot of work to generate
\nthe cipher – you need to generate frequency tables, and work out the number of
\nsubstitions, etc. It’s definitely not trivial to set up, and it’s still pretty
\neasy to crack.<\/p>\n
For that reason, those kinds of solutions aren’t used much – there’s a lot <\/p>\n A rotating cipher is one of the simplest examples of a form of encryption So let’s look at the simplest kind of stateful cipher: a simple rotating The precise way that you rotate that outer ring varies depending on the For example, here’s some Python code which implements rotating ciphers. It’s The quality of a rotating cipher depends largely on quality of the For example, the infamous German Enigma machines had three or four physical rotors. Each time a character was encrypted, one of the rotors moved, and its motion could trigger motions of the other two rotors, depending on the setting of an encryption key. The positions of the rotor wheels would create an electrical circuit which actually generated the encrypted character. In the most sophisticated version of Enigma, the rotors were replaceable – which allowed you to reconfigure the relationships between the rotors; you also could set an initial position on the rotor wheels (the passcode), and the more advanced machines included an electrical plugboard that could reconfigure the electrical So, last time, we looked at simple substitution ciphers. In a substitution cipher, you take each letter, and pick a replacement for it. To encrypt a message, you just substitute the replacement for each instance of each letter. As I explained, it’s typically pretty each to break that encryption – the basic secret of the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-669","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aN","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/669","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=669"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/669\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=669"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nof prep work, and the secret that you need to share with your partner is large
\nand complicated. You can get better<\/em> quality with less effort and a
\nsimple secret using a different scheme called a rotating cipher.<\/p>\n
\nthat CS geeks like me call stateful<\/em> encryption. The idea is that you
\nstart with a simple substitution. But then each time you encrypt a character,
\nyou change<\/em> the substitution. This covers an incredibly wide range of
\nencryption techniques – you can understand most digital encryption schemes as
\nbeing some kind of stateful cipher.<\/p>\n
\ncipher. In a rotating cipher, you have an alphabet, consisting of the set of
\ncharacters that you can use in messages. You have a basic cipher, which consists
\nof the set of characters arranged in some order. You take the alphabet in order,
\nand line it up with the cipher. Each time you encode a character, you shift the
\nway that the cipher and the basic alphabet line up. The reason it’s called a
\nrotating cipher is that the physical version of this consists of two wheels: the
\ninner wheel has the un-encrypted alphabet; the outer wheel has the cipher. To
\nencrypt a character, you look it up on the inner ring, and write down the
\ncorresponding character on the outer ring. After that, you rotate the outer
\nring.<\/p>\n
\nexact encryption technique being used. There are a variety of techniques that
\nyou can use for rotating the cipher. Two simple examples:<\/p>\n\n
\nrotate the cipher wheel three steps after each character is encrypted.<\/li>\n
\nif you encrypt the character at position five in the alphabet, rotate
\nthe cipher by five steps.<\/li>\n<\/ol>\n
\nimplemented as an abstract superclass with two subclasses using two different
\nrotation methods. The first is a fixed rotator – it rotates by three characters
\neach time. The second is a variable rotation: it rotates by 3 times the position
\nof the encoded character in the alphabet.<\/p>\n\nclass RotatingCipher(object):\ndef __init__(self, alphabet, cipher):\nself._alphabet = alphabet\nself._cipher = cipher\n# to be overridden by subclasses for different rotation\n# schemes.\ndef _RotateCipher(self, c):\npass\ndef CryptNextChar(self, c):\n\"\"\"Encrypt a single character and rotate the cipher.\"\"\"\n# find position of \"c\" in the alphabet.\nindex = self._alphabet.find(c)\n# encrypted character is that position plus the rotation,\n# modulo the size of the alphabet.\ncrypt = self._cipher[(index + self._rot) % len(self._alphabet)]\nself._RotateCipher(c)\nreturn crypt\ndef Encrypt(self, s):\n\"\"\"Encrypt a message string.\"\"\"\nself._rot = 0\nresult = \"\"\nfor c in s:\nresult += self.CryptNextChar(c)\nreturn result\ndef DecryptNextChar(self, c):\n\"\"\"Decrypt a single character and rotate the cipher.\"\"\"\n# to decrypt of character, find index of the crypted character in\n# the cipher, and subtract the rotation from it, giving the\n# index of the decrypted character in the alphabet.\nindex = self._cipher.find(c)\nindex -= self._rot\nif index < 0: index = len(self._alphabet) + index\nself._RotateCipher(self._alphabet[index])\nreturn self._alphabet[index]\ndef Decrypt(self, s):\n"""Decrypt a string encrypted by this cipher."""\nself._rot = 0\nresult = ""\nfor c in s:\nresult += self.DecryptNextChar(c)\nreturn result\nclass FixedRotatingCipher(RotatingCipher):\n"""An implementation of a cipher using a rotation strategy\nthat shifts the cipher by a fixed increment after each\ncharacter."""\ndef __init__(self, alphabet, cipher, increment):\nsuper(FixedRotatingCipher, self).__init__(alphabet, cipher)\nself._rot = 0\nself._increment = increment\ndef _RotateCipher(self, c):\nself._rot = (self._rot + self._increment) % len(self._alphabet)\nclass VariableRotatingCipher(RotatingCipher):\n"""An implementation of a cipher using a function of the\nlast character as the rotator. Each rotation shifts by\nthe character index times three."""\ndef __init__(self, alphabet, cipher):\nsuper(VariableRotatingCipher, self).__init__(alphabet, cipher)\ndef _RotateCipher(self, c):\nindex = self._alphabet.find(c)\nself._rot = (self._rot + (3*index)) % len(self._alphabet)\nfcipher = FixedRotatingCipher(\n"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,- ",\n"KLMNijklSTUVabcduvwxyzABCDEFefghGHIJ.,- mnopOPQRqrstWXYZ", 3)\nen = fcipher.Encrypt("Mark has a big nose.")\nde = fcipher.Decrypt(en)\nprint "Encrypted = %s" % en\nprint "Decrypted = %s" % de\nvcipher = VariableRotatingCipher(\n"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,- ",\n"KLMNijklSTUVabcduvwxyzABCDEFefghGHIJ.,- mnopOPQRqrstWXYZ")\nven = vcipher.Encrypt("Mark has a big nose.")\nvde = vcipher.Decrypt(ven)\nprint "Variable encrypted = %s" % ven\nprint "Variable decrypted = %s" % vde\n<\/pre>\n
\nthe rotation strategy. A fixed offset rotator frankly stinks – it’s only marginally better than a simple substitution cipher. But with a really good, sophisticated rotator, you can make an amazingly good cipher. Up to the advent of modern computers, rotating ciphers were pretty much top of the heap of encryption – but with much, much more sophisticated rotators. <\/p>\n
\npart of the machine. So the “rotation” corresponded to a rewiring of the machine by switching the positions of the rotors, which interacted in a complicated way which was dependent partly on the physical markings on the rotor disks, partly on the encryption key, and partly on the last encrypted character.<\/p>\n","protected":false},"excerpt":{"rendered":"