lib/crypto.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Mix of all things cryptography-related
  16 module crypto
  17
  18 redef class Char
  19         # Rotates self of `x`
  20         #
  21         # NOTE: works on letters only
  22         #
  23         #     assert 'x'.rot(6) == 'd'
  24         #     assert 'T'.rot(15) == 'I'
  25         #     assert '1'.rot(10) == '1'
  26         #     assert '$'.rot(10) == '$'
  27         #     assert 'z'.rot(-2) == 'x'
  28         fun rot(x: Int): Char do
  29                 if not is_letter then return self
  30                 x = x % 26
  31                 if x < 0 then x += 26
  32                 var up = false
  33                 var val = code_point
  34                 if is_upper then
  35                         up = true
  36                         val += 32
  37                 end
  38                 val += x
  39                 if val > 122 then val -= 26
  40                 if up then val -= 32
  41                 return val.code_point
  42         end
  43 end
  44
  45 redef class Text
  46         # Performs a Rotation of `x` on each letter of self
  47         #
  48         # Works by replacing every character in `self` by its
  49         # rotated char.
  50         #
  51         # Say we have a rotation of `3` (Caesar rotation, for
  52         # culture) for a string : "aybabtu"
  53         #
  54         # a, rotated by 3 becomes d
  55         # y, rotated by 3 becomes b
  56         # b, rotated by 3 becomes e
  57         # t, rotated by 3 becomes w
  58         # u, rotated by 3 becomes x
  59         #
  60         # We then replace every letter in our original string by
  61         # their rotated representations, therefore yielding : "dbedewx"
  62         #
  63         #     assert "All your base are belong to us".rot(13) == "Nyy lbhe onfr ner orybat gb hf"
  64         #     assert "This is no moon.".rot(4).rot(22) == "This is no moon."
  65         #
  66         # NOTE : Works on letters only
  67         # NOTE : This cipher is symmetrically decrypted with an `x` of 26-`x`
  68         fun rot(x: Int): Text do
  69                 var rot = x % 26
  70                 if rot < 0 then rot += 26
  71                 var d = new FlatBuffer.with_capacity(length)
  72                 for i in chars do
  73                         d.add i.rot(rot)
  74                 end
  75                 return d.to_s
  76         end
  77
  78         # Returns a rail-fence cipher from `self` with `depth` rails
  79         #
  80         # Rail works by drawing a zig-zag pattern on `depth` rails.
  81         #
  82         # Say we have "fuckingbehemoth".railfence(4)
  83         #
  84         # This happens in-memory:
  85         #
  86         # ~~~raw
  87         # f.....g.....o..
  88         # .u...n.b...m.t.
  89         # ..c.i...e.e...h
  90         # ...k.....h.....
  91         # ~~~
  92         #
  93         # Therefore, yielding the ciphertext : "fgounbmtcieehkh"
  94         #
  95         #     assert "fuckingbehemoth".railfence(4) == "fgounbmtcieehkh"
  96         fun railfence(depth: Int): Text do
  97                 var lines = new Array[FlatBuffer].with_capacity(depth)
  98                 var up = false
  99                 for i in [0..depth[ do
 100                         lines[i] = new FlatBuffer.with_capacity(length)
 101                 end
 102                 var curr_depth = 0
 103                 for i in chars do
 104                         for j in [0..depth[ do
 105                                 if j == curr_depth then
 106                                         lines[j].add i
 107                                 else
 108                                         lines[j].add '.'
 109                                 end
 110                         end
 111                         if up then
 112                                 curr_depth -= 1
 113                         else
 114                                 curr_depth += 1
 115                         end
 116                         if curr_depth == 0 then
 117                                 up = false
 118                         end
 119                         if curr_depth == (depth - 1) then
 120                                 up = true
 121                         end
 122                 end
 123                 var r = new FlatBuffer.with_capacity(length)
 124                 for i in lines do
 125                         r.append i.to_s.replace(".", "")
 126                 end
 127                 return r.to_s
 128         end
 129
 130         # Transforms a rail-fence-encrypted Text to its original
 131         #
 132         #     assert "fgounbmtcieehkh".unrail(4) == "fuckingbehemoth"
 133         fun unrail(depth: Int): Text do
 134                 var dots = "." * length
 135                 var arr = new FlatBuffer.from(dots)
 136                 var start = 0
 137                 var paces = depth.unrail_paces
 138                 for i in [0..depth[ do
 139                         var lp = paces[i].first
 140                         var rp = paces[i].second
 141                         var pos = i
 142                         var l = true
 143                         while pos < length do
 144                                 arr[pos] = chars[start]
 145                                 if l then
 146                                         pos += lp
 147                                         l = false
 148                                 else
 149                                         pos += rp
 150                                         l = true
 151                                 end
 152                                 start += 1
 153                         end
 154                 end
 155                 return arr.to_s
 156         end
 157 end
 158
 159 redef class Bytes
 160
 161         # Returns `self` xored with `key`
 162         #
 163         # The key is cycled through until the `self` has been completely xored.
 164         #
 165         #     assert "goodmorning".to_bytes.xorcipher(" ".to_bytes) == "GOODMORNING".bytes
 166         fun xorcipher(key: Bytes): Bytes do
 167                 var xored = new Bytes.with_capacity(self.length)
 168
 169                 for i in self.length.times do
 170                         xored.add(self[i] ^ key[i % key.length])
 171                 end
 172
 173                 return xored
 174         end
 175
 176         # Computes the edit/hamming distance of two sequences of bytes.
 177         #
 178         #     assert "this is a test".to_bytes.hamming_distance("wokka wokka!!!".bytes) == 37
 179         #     assert "this is a test".to_bytes.hamming_distance("this is a test".bytes) == 0
 180         #
 181         fun hamming_distance(other: SequenceRead[Byte]): Int do
 182                 var diff = 0
 183                 for idx in self.length.times do
 184                         var res_byte = self[idx] ^ other[idx]
 185                         for bit in [0..8[ do
 186                                 if res_byte & 1u8 == 1u8 then diff += 1
 187                                 res_byte = res_byte >> 1
 188                         end
 189                 end
 190                 return diff
 191         end
 192
 193 end
 194
 195 redef class Int
 196         # Generates the paces for each depth.
 197         #
 198         # Each entry of the returned array is a couple of the first pace
 199         # and the second one, they are alternated when deciphering a rail-encrypted string.
 200         #
 201         # Say we have the encrypted string "fgounbmtcieehkh" on 4 rails
 202         #
 203         # To find the distance between each character on the original railed
 204         # string, we need to compute the extremes.
 205         #
 206         # The extremes always have a distance of `depth - 1`, multiplied by 2, no pairing.
 207         #
 208         # In the example, that would be : [(4 - 1) * 2, (4 - 1) * 2] => [6,6]
 209         #
 210         # For every rail in-between, the first distance is the largest absolute value
 211         # of the difference between the current depth and the extremes, multiplied by 2.
 212         #
 213         # Its pair is the distance of maximum and the distance yielded by the previous
 214         # calculation.
 215         #
 216         # In our example, that would be :
 217         #
 218         # Maximums : (4 - 1) * 2 = 3 * 2 => [6,6]
 219         # In between : Distance for depth 2 : max(2 - 1, 4 - 2) => 2
 220         # The calculation yields the couple [(2 * 2), 6 - 4] => [4, 2]
 221         # The symmetric couple is reversed : [2, 4]
 222         #
 223         # In fine, the example yields the array : [[6,6], [4,2], [2,4], [6,6]]
 224         #
 225         # In the end, our string is read using the generated array
 226         #
 227         # SEE: `Text::unrail` for how the array is used
 228         private fun unrail_paces: Array[Couple[Int, Int]] do
 229                 var ret = new Array[Couple[Int,Int]].with_capacity(self)
 230                 var extremes = new Couple[Int, Int]((self - 1) * 2, (self - 1) * 2)
 231                 for i in [0..self[ do
 232                         ret.add extremes
 233                 end
 234                 var mid = ((self.to_f)/2.0).floor.to_i
 235                 for i in [1 .. mid[ do
 236                         var rd = i + 1
 237                         var lodepth = self - rd
 238                         var hidepth = (rd - self).abs
 239                         var dd: Int
 240                         if hidepth > lodepth then
 241                                 dd = hidepth * 2
 242                         else
 243                                 dd = lodepth * 2
 244                         end
 245                         var cp = new Couple[Int, Int](dd, extremes.first-dd)
 246                         var ccp = new Couple[Int, Int](extremes.first - dd, dd)
 247
 248                         ret[i] = cp
 249                         ret[self - rd] = ccp
 250                 end
 251                 if not self.is_even then
 252                         ret[mid] = new Couple[Int, Int](extremes.first/2, extremes.first/2)
 253                 end
 254                 return ret
 255         end
 256 end