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 = ascii
  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.ascii
  42         end
  43 end
  44
  45 redef class String
  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): String 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         #       f.....g.....o..
  86         #       .u...n.b...m.t.
  87         #       ..c.i...e.e...h
  88         #       ...k.....h.....
  89         #
  90         # Therefore, yielding the ciphertext : "fgounbmtcieehkh"
  91         #
  92         #    assert "fuckingbehemoth".railfence(4) == "fgounbmtcieehkh"
  93         fun railfence(depth: Int): String do
  94                 var lines = new Array[FlatBuffer].with_capacity(depth)
  95                 var up = false
  96                 for i in [0..depth[ do
  97                         lines[i] = new FlatBuffer.with_capacity(length)
  98                 end
  99                 var curr_depth = 0
 100                 for i in chars do
 101                         for j in [0..depth[ do
 102                                 if j == curr_depth then
 103                                         lines[j].add i
 104                                 else
 105                                         lines[j].add '.'
 106                                 end
 107                         end
 108                         if up then
 109                                 curr_depth -= 1
 110                         else
 111                                 curr_depth += 1
 112                         end
 113                         if curr_depth == 0 then
 114                                 up = false
 115                         end
 116                         if curr_depth == (depth - 1) then
 117                                 up = true
 118                         end
 119                 end
 120                 var r = new FlatBuffer.with_capacity(length)
 121                 for i in lines do
 122                         r.append i.to_s.replace(".", "")
 123                 end
 124                 return r.to_s
 125         end
 126
 127         # Transforms a rail-fence-encrypted String to its original
 128         #
 129         #    assert "fgounbmtcieehkh".unrail(4) == "fuckingbehemoth"
 130         fun unrail(depth: Int): String do
 131                 var dots = "." * length
 132                 var arr = new FlatBuffer.from(dots)
 133                 var start = 0
 134                 var paces = depth.unrail_paces
 135                 for i in [0..depth[ do
 136                         var lp = paces[i].first
 137                         var rp = paces[i].second
 138                         var pos = i
 139                         var l = true
 140                         while pos < length do
 141                                 arr[pos] = chars[start]
 142                                 if l then
 143                                         pos += lp
 144                                         l = false
 145                                 else
 146                                         pos += rp
 147                                         l = true
 148                                 end
 149                                 start += 1
 150                         end
 151                 end
 152                 return arr.to_s
 153         end
 154 end
 155
 156 redef class Int
 157         # Generates the paces for each depth.
 158         #
 159         # Each entry of the returned array is a couple of the first pace
 160         # and the second one, they are alternated when deciphering a rail-encrypted string.
 161         #
 162         # Say we have the encrypted string "fgounbmtcieehkh" on 4 rails
 163         #
 164         # To find the distance between each character on the original railed
 165         # string, we need to compute the extremes.
 166         #
 167         # The extremes always have a distance of `depth - 1`, multiplied by 2, no pairing.
 168         #
 169         # In the example, that would be : [(4 - 1) * 2, (4 - 1) * 2] => [6,6]
 170         #
 171         # For every rail in-between, the first distance is the largest absolute value
 172         # of the difference between the current depth and the extremes, multiplied by 2.
 173         #
 174         # Its pair is the distance of maximum and the distance yielded by the previous
 175         # calculation.
 176         #
 177         # In our example, that would be :
 178         #
 179         # Maximums : (4 - 1) * 2 = 3 * 2 => [6,6]
 180         # In between : Distance for depth 2 : max(2 - 1, 4 - 2) => 2
 181         # The calculation yields the couple [(2 * 2), 6 - 4] => [4, 2]
 182         # The symmetric couple is reversed : [2, 4]
 183         #
 184         # In fine, the example yields the array : [[6,6], [4,2], [2,4], [6,6]]
 185         #
 186         # In the end, our string is read using the generated array
 187         #
 188         # SEE: `String::unrail` for how the array is used
 189         private fun unrail_paces: Array[Couple[Int, Int]] do
 190                 var ret = new Array[Couple[Int,Int]].with_capacity(self)
 191                 var extremes = new Couple[Int, Int]((self - 1) * 2, (self - 1) * 2)
 192                 for i in [0..self[ do
 193                         ret.add extremes
 194                 end
 195                 var mid = ((self.to_f)/2.0).floor.to_i
 196                 for i in [1 .. mid[ do
 197                         var rd = i + 1
 198                         var lodepth = self - rd
 199                         var hidepth = (rd - self).abs
 200                         var dd: Int
 201                         if hidepth > lodepth then
 202                                 dd = hidepth * 2
 203                         else
 204                                 dd = lodepth * 2
 205                         end
 206                         var cp = new Couple[Int, Int](dd, extremes.first-dd)
 207                         var ccp = new Couple[Int, Int](extremes.first - dd, dd)
 208
 209                         ret[i] = cp
 210                         ret[self - rd] = ccp
 211                 end
 212                 if not self.is_even then
 213                         ret[mid] = new Couple[Int, Int](extremes.first/2, extremes.first/2)
 214                 end
 215                 return ret
 216         end
 217 end