1

我正在尝试对 Enigma 编码机进行编程。我已经设法让转子和反射器工作正常，但我正在尝试计算转子的前进。

对于任何不熟悉这个的人。Enigma Machine 由 3 个作为替换密码的转子和一个包含 13 对字符的反射器组成。为了对字符进行编码，首先由第一个转子对其进行编码，然后将由此编码的字符传递到第二个转子，然后再通过一个转子到达反射器，该反射器将这个新字符与与之配对的字符交换。然后，这个配对字符通过转子以相反的方式反向编码，直到最终得到最终编码字符。

在对单个字符进行编码之前，转子会移动。如果你有一个很长的消息，在任何东西被编码之前，第一个转子被移动一个位置，然后这个字符通过系统并被编码。然后在第二个字符被编码之前，第一个转子再次移动。转子不断移动，直到它再次到达启动位置。在第 25 个字符被编码后，第一个转子到达它开始的位置，但现在第二个转子移动了一个位置。在第二个转子再次转动之前，第一个转子再转动 26 次。当第二个转子转动 26 次时，第三个转子转动一次。这种情况一直发生，直到达到 25 25 25 ，此时它们重置回 0 0 0 并且循环再次开始。这让我想起了一个分小时的时钟，

我知道这可能可以用模算术编程，但我看不出怎么做？因此，任何帮助将不胜感激。

4

3 回答 3

2

从机器的角度来看，转子是两个东西：

  • 它是从一个符号到另一个符号的函数
  • 它可以进一步成为另一个功能

我们可以为它写一个类似的类型：

newtype Symbol = Symbol {representation :: Int}

data Rotor = Rotor {
    transformation :: Symbol -> Symbol,
    next :: Rotor
}

如果机器知道反射的对称性，它可能类似于

data Rotor = Rotor {
    forward :: Symbol -> Symbol,
    backward :: Symbol -> Symbol,
    next :: Rotor
}

（你也可以使用类似的东西[(Symbol -> Symbol,Symbol -> Symbol)]）

现在，我们如何构造一个Rotor？让我们来定义一个示例转子 IC。

rotorICdefinition = map symbol $ "DMTWSILRUYQNKFEJCAZBPGXOHV"

现在，符号需要有 type Char -> Symbol。这样的事情应该做。

symbol :: Char -> Symbol
symbol x = Symbol $ ord x - ord 'A'

里面有一堆魔法ord。它已经知道字母表的顺序。例如：

Prelude Data.Char> map ord "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
[65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90]

接下来，我们希望能够根据其定义制作转子

rotorIC :: Rotor
rotorIC = makeRotor rotorICdefinition

所以makeRotor应该有类型

makeRotor :: [Symbol] -> Rotor

我们可以将其定义为

makeRotor definition = makeRotor' 0
    where
        makeRotor' steps = Rotor {
            forward = forwardLookup steps,
            backward =  reverseLookup steps,
            next = makeRotor' ((steps+1) `mod` symbolModulus)
        }
        forwardLookupTable = array (minBound, maxBound) (zip symbols definition)
        reverseLookupTable = array (minBound, maxBound) (zip definition symbols)
        forwardLookup = lookup forwardLookupTable
        reverseLookup = lookup reverseLookupTable
        lookup lookupTable steps = (lookupTable !) . Symbol . (`mod` symbolModulus) . (+ steps) . representation

这里发生了很多事情。我们正在制作无限的转子流，每一个都比前一个旋转了一步，从一个旋转了 0 步的转子开始。stepsinmakeRotor'正在跟踪它旋转了多少步。包括Rotor和转换forward，backward其中考虑了转子旋转了多少步。转子是相同的next，但已经多转了一步。为了避免最终溢出整数，我们将其模mod数取为存在的符号数symbolModulus。（有更有效的方法可以做到这一点）。这两个查找基于构建一次的查找表，将范围内的每个符号映射(minBound, maxBound)到根据definition. 这lookup本身只是获取输入，添加步数，取模数作为符号数，然后返回查找表中该位置的内容。

这要求我们定义新出现minBound的 、maxBound、symbols和symbolModulus：

instance Bounded (Symbol) where
    minBound = symbol 'A'
    maxBound = symbol 'Z' 

symbolModulus = (representation maxBound) - (representation minBound) + 1

-- This could have some other definition
symbols = map symbol $ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

我们将添加一个小 UI，并将整个程序放在一起：

module Main (
    main
) where

import Data.Char
import Data.Array -- requires array package
import System.IO

main = go rotorIC
    where go rotor = do
            putStr "Input   : "
            hFlush stdout
            command <- getLine
            case command of
                "next" -> go (next rotor)
                [] -> return ()
                text -> case all (inRange (char minBound, char maxBound)) text of
                    True -> do
                        putStrLn . ("Forward : " ++) $ map (char . forward rotor . symbol) text
                        putStrLn . ("Backward: " ++)$ map (char . backward rotor . symbol) text
                        go rotor
                    _ -> do
                        putStrLn "Not all of the input was symbols"
                        go rotor 


newtype Symbol = Symbol {representation :: Int} deriving (Eq, Ord, Ix)

symbol :: Char -> Symbol
symbol x = Symbol $ ord x - ord 'A'

char :: Symbol -> Char
char x = chr $ representation x + ord 'A' 

instance Bounded (Symbol) where
    minBound = symbol 'A'
    maxBound = symbol 'Z' 

symbolModulus = (representation maxBound) - (representation minBound) + 1

-- This could have some other definition 
symbols = map symbol $ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

data Rotor = Rotor {
    forward :: Symbol -> Symbol,
    backward :: Symbol -> Symbol,
    next :: Rotor
}


rotorICdefinition = map symbol $ "DMTWSILRUYQNKFEJCAZBPGXOHV"

rotorIC :: Rotor
rotorIC = makeRotor rotorICdefinition

makeRotor :: [Symbol] -> Rotor

makeRotor definition = makeRotor' 0
    where
        makeRotor' steps = Rotor {
            forward = forwardLookup steps,
            backward =  reverseLookup steps,
            next = makeRotor' ((steps+1) `mod` symbolModulus)
        }
        forwardLookupTable = array (minBound, maxBound) (zip symbols definition)
        reverseLookupTable = array (minBound, maxBound) (zip definition symbols)
        forwardLookup = lookup forwardLookupTable
        reverseLookup = lookup reverseLookupTable
        lookup lookupTable steps = (lookupTable !) . Symbol . (`mod` symbolModulus) . (+ steps) . representation

现在我们可以通过几个例子来运行。字母表前六个字母的正向变换是我们的开始rotorICdefinition：

Input   : ABCDEFG
Forward : DMTWSIL
Backward: RTQAONV

如果我们把 的开头放入rotorICdefinition，我们会得到字母表的前六个字母作为后向变换：

Input   : DMTWSIL
Forward : WKBXZUN
Backward: ABCDEFG

如果我们在转子上进行下一步，我们会得到一些非常不同的东西：

Input   : next
Input   : ABCDEFG
Forward : MTWSILR
Backward: TQAONVY

但是如果我们在 'A' 之前输入一个开头的字母，我们会再次回到我们的定义：

Input   : ZABCDEF
Forward : DMTWSIL
Backward: RTQAONV

在转子上进行下一步 25 次后，我们又回到了开始的地方：

Input   : next
(25 times total)
Input   : next
Input   : ABCDEFG
Forward : DMTWSIL
Backward: RTQAONV
于 2013-11-17T23:47:16.170 回答
0

您需要分别测试每个转子（或者您可以编写一个复杂的表达式来一次更新它们，但这不可读）：

type RotorState = (Int, Int, Int)

nextState :: RotorState -> RotorState
nextState (x, y, z)
  | x == 25 && y == 25 && z == 25 = (0, 0, 0)
  | y == 25 && z == 25 = (x + 1, 0, 0)
  | z == 25 = (x, y + 1, 0)
  | otherwise = (x, y, z+ 1)

要使用，您将拥有如下功能：

actUponRotor :: RotorState -> (RotorState, a)
actUponRotor r = (nextState r, undefined)

whereundefined代表要对当前转子位置进行的计算（输出单个字符或接收一个字符）

如果您不喜欢明确地携带状态，您可能希望使用Statemonad，如下所示：

actUponRotor' :: State RotorState a
actUponRotor' = do
  changeRotorState
  return undefined

changeRotorState :: State RotorState ()
changeRotorState = modify nextState
于 2013-11-17T23:48:48.097 回答
-1

您可以在命令式语言中使用 Haskell 的通用计数器等价物。

假设你有一些命令式代码

def f(x) {
c = 0 ;

while ( c<k ) {
    x = g(x,c) ;
    c +=1; 

return z(x);
}

Haskell 版本将是

f x = f' 0 x where f' k x = z x ; f _ x = f (_+1) (g x )

所以你可以将转子的位置作为这样的内部参数。

您也可以使用模式匹配。

RotorState = (Int,Int,Int)
turnRotor :: RotorState ->RotorState
turnRotor (25, 25 , 25    )  = (0  , 0 ,  0)
turnRotor (_ , 25 , 25    )  = (_+1, 0 ,  0)
turnRotor (_ , __ , 25    )  = (_  , __+1,0)
turnRotor (_ , __  , ___  )  = (_  , __, ___+1)

玩得开心！我希望这会有所帮助。

于 2013-11-17T21:48:42.653 回答