Tag Info

Hot answers tagged

57

I strongly disagree with the other answer which trivializes the contributions of Alan Turing and his group, as well as the Polish mathematicians who first worked on the problem. Of course increasing the numbers makes the problem harder, but even with a modern computer a brute force attack on the often cited 150 million million combinations (this number ...


43

What you're calling $\dfrac 13$ is just the multiplicative inverse of $3$ mod $3016$. You can easily verify that $2011$ is the multiplicative inverse of $3$. $$3\cdot 2011 = 6033 = (2\cdot 3016)+1$$


28

In modern computer cryptography, large numbers are one of the most important factors. That's why 40-bit encryption used to be considered security back in 1995, but today (with 512 bit encryption available on almost any security device) would be considered a joke. My reading of the history of cracking Enigma is that failures in use and implementation of ...


25

One can in fact use fractions in modular arithmetic, as long as one only uses fractions with denominator coprime to the modulus. For these fractions the usual grade school arithmetic of fractions holds true. For example, let's consider your problem. $\quad {\rm mod}\ 3n\!+\!1\!:\,\ 3n\!+\!1\equiv 0\ $ so $\ 1 \equiv 3(-n)\ $ therefore $\ \dfrac{1}3 \equiv ...


13

The answer to the question "Mathematically, why was the Enigma machine so easy to crack?": The first major weakness was the fact that the same settings were used for a whole day. There are always messages that are easier to crack and others that are harder to crack; using the same settings for a day meant only one exceptionally easy to crack (and likely ...


11

In every possible state, an Enigma machine produces a permutation of the letters A to Z. And not just any permutation, but one that exchanges pairs of letters, for example in a certain setting it might exchange A and Q, B and F, C and R and so on. Such a permutation, which consists entirely of cycles of length 2, is called an "Enigma Permutation". After ...


3

The other answers give an idea of the techniques involved but I want to insist on a very deep and confusing observation from the field of cryptanalysis: Iterated application of very simple (reversible) operations are often very hard to decypher. In essence, this means that you can take a single operation, say $$ x_{n+1}\mapsto a\cdot x_{n}+b \mod k$$ ...


3

The first reads, "given that the encryption function $E_k$ using key $k$ applied to message $m$ returns the cipher $c$, the probability that two messages, $m$ and $m^∗$, are equal is $\frac{1}{|M|}$." The second line reads "The probability that two messages, $m$ and $m^∗$ are the same is equal to the probability that their encrypted messages, $E_k(m)$ and ...


3

Start by factoring $n = 462257 = 503 \cdot 919 $. You can calculate $\varphi(n)$ and $d$ now since you know that $d \equiv e^{-1} \pmod{\varphi(n)}$. Given $d$, you can decrypt $m$ as usual. Alternatively, use the method suggested by Barry Cipra in the comments (brute force $m^{13} \equiv 139552 \pmod{462257}$).


3

We have an associative operation here – it is the function composition $\circ$. For any functions $f : X \to Y$ and $g : Y \to Z$ we have $g \circ f : X \to Z$, defined by $(g \circ f)(x) := g(f(x))$ for all $x \in X$. I heard some authors defined it the other way around, $(f \circ g)(x) := g(f(x))$. I think my version is more common.) This operation is ...


2

This is only a very rough, back of the envelope answer because there were several versions of the enigma and the Bombe, but according to the Wikipedia article on the British Bombe, one version of the Bombe could run through all 17,576 possible positions for one rotor order was about 20 minutes Since $17576 = 26^3$, it's referring to the three-rotor ...


2

At any stage the Enigma machine provided a unique electrical path through the plugboard and rotors from each letter key to the reflector. The reflector then sent the current back down a different path through the rotors and plugboard, so it ended up at a different letter key and that new letter's light. This had two effects: at any stage keys were ...


2

I assume you know how RSA works and you just want to understand how to do computations explicitely. Since we know $91=13\cdot 7$ we can easily get $\varphi(91)=12\cdot 6=72$. The private (decryption) key in RSA is obtained by computing the inverse of the public (encryption) key modulo $\phi(N)$, where $N=p\cdot q$ is the public "maximun number" as you ...


2

The result of Yitang Zhang (and improved by James Maynard) in 2013 was that there exist infinitely many primes which differ by some fixed number $\leq 600$. This isn't helpful in your problem. The number of primes smaller than $n$ is given by the prime counting function, $\pi(n)$. It is known that $\frac{\pi(n)}{n/\log n} \to 1$ as $n \to \infty$, so ...


2

The reason it was so difficult to break the enigma was that the output depended on the "Start State" of the machine. So if you keep on typing the letter "A" multiple times it would give a different output. Plus they used to change the gear every 24 hours. This would make the number of possible outputs for an input very large. The time that would be ...


2

In your notation, if $m<n$, then the key phrase is repeated in whole or in part as often as is necessary to make a key of length $n$. Thus, $k_{m+1}=k_1,k_{m+2}=k_2$, and son on. This is explained at your second link (where I’ve corrected a few typos): $K_i$ – $i$-th character of the key phrase (if the key phrase is shorter than the open text, which ...


2

In addition to these relative frequencies, you need the actual numerical frequencies of the individual letters. If $n_k$ is the actual number of instances of letter $k$, and $n$ is the total number of letters, for each letter you need the quantity $$\frac{n_k}n\cdot\frac{n_k-1}{n-1}=f_k\cdot\frac{n_k-1}{n-1}\;.$$ The index of coincidence is then ...


1

The basic idea of congruences is to say that one number is equivalent to another by a relation. Numbers that are equivalent are said to belong to the same equivalence class. In the case of mod, the equivalence relation is "leave the same remainder when divided by n". So if we consider for example 22 and 48 mod 13, they both leave remainder 9. $22=13+9$, and ...


1

The reason $e$ must be coprime to $\phi(n)$ is that otherwise you can never have the key equation $ed = k\phi(n) + 1$, which is equivalent to saying that $ed$ is congruent to $1$ mod $\phi(n)$. If you rewrite this equation as $1 = ed-k\phi(n)$, then any common divisor of $e$ and $\phi(n)$ divides the right hand side. But the left hand side has no ...


1

For a fixed choice of $k_1,\ldots, k_{16}$, DES is a map $P\mapsto C$ and it is this map that is bijective because there exists a (two-sided) inverse map.



Only top voted, non community-wiki answers of a minimum length are eligible