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