1

Enigma Coding Machine をプログラムしようとしています。ローターとリフレクターを正常に動作させることができましたが、ローターの前進を解決しようとしています.

これに精通していない人のために。Enigma Machine は、置換暗号である 3 つのローターと、13 組の文字を含むリフレクターで構成されます。文字をエンコードするには、最初のローターによって最初にエンコードされます。次に、エンコードされた文字が 2 番目のローターに渡され、さらにもう 1 つのローターを介してリフレクターに渡されます。リフレクターは、この新しい文字をペアになっている文字と交換します。このペアになった文字は、最終的にエンコードされた文字になるまで、ローターを介して逆方向にエンコードされます。

個々の文字がエンコードされる前に、ローターがシフトされます。非常に長いメッセージがある場合、何かがエンコードされる前に、最初のローターが 1 つシフトされ、この文字がシステムを通過してエンコードされます。次に、2 番目の文字がエンコードされる前に、最初のローターが再びシフトされます。ローターは、再びスタートに達するまで継続的にシフトされます。25 番目の文字がエンコードされた後、最初のローターは開始位置に到達しますが、2 番目のローターは 1 桁移動します。次に、最初のローターがさらに 26 回回転してから、2 番目のローターが再び回転します。2 番目のローターが 26 回回転すると、3 番目のローターが 1 回転します。これは、25 25 25 に達するまで発生し続け、その時点で 0 0 0 にリセットされ、サイクルが再び開始されます。これは時を刻む時計を思い起こさせます。

これはおそらく剰余演算でプログラムできることは知っていますが、方法がわかりませんか? そのため、どんな助けでも大歓迎です。

4

3 に答える 3

2

マシンの観点から見ると、ローターは次の 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

ここでは多くのことが起こっています。ローターの無限のストリームを作成しています。各ローターは前のローターから 1 ステップ回転し、0 ステップ回転したローターから始めます。stepsでは、makeRotor'回転したステップ数を追跡しています。はRotorと の両方forwardで構成されbackward、ローターが回転したステップ数を考慮に入れます。ローターは同じですが、もうnext一段回転しています。最終的に整数がオーバーフローしないようにするためにmod、存在するシンボルの数を法としsymbolModulusます。（それを行うより効率的な方法があります）。2 つのルックアップは、一度構築されたルックアップ テーブルに基づいており、範囲内のすべてのシンボル(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

ここで、いくつかの例を見てみましょう。アルファベットの最初の 6 文字の順方向変換が の始まりですrotorICdefinition。

Input   : ABCDEFG
Forward : DMTWSIL
Backward: RTQAONV

の先頭に入れるとrotorICdefinition、後方変換としてアルファベットの最初の 6 文字が返されます。

Input   : DMTWSIL
Forward : WKBXZUN
Backward: ABCDEFG

ローターの次のステップに進むと、非常に異なる結果が得られます。

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

しかし、'A' の 1 つ前に文字を入れると、再び定義が返されます。

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)

現在のローターundefined位置で実行される計算を表します (単一文字の出力または受信)。

状態を明示的に持ち歩きたくない場合は、次のStateようにモナドを使用することをお勧めします。

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 に答える