# Tag Info

14

If you combine two affine ciphers, you obtain one affine cipher. Say the first cipher is $e_1(x) = a_1x+b_1$ and the second is $e_2(x) = a_2x+b_2$. Then $e_1(e_2(x)) = a_1(a_2x+b_2)+b_1 = (a_1a_2)x+(a_1b_2+b_1)$. Note that if $a_1$ and $a_2$ are both relatively prime with the modulus, then so is $a_1a_2$, so the new cipher can also be deciphered.

6

does the cipher become entirely affine and hence trivially weak? Yes; the AES sbox is the only source of nonlinearity (the ShiftRows and MixColumns are linear, and AddRoundKeys for a fixed key is affine), and so if you replace it with a linear/affine one, the entire cipher becomes affine.

6

This is a special case of the affine cipher where $m=26$. Let's encrypt a single letter using your $E$. Let it be m, say, which is at index 12. So, $$E(12) = (7 \cdot 12 + 10) \mod{26} = 16$$ Now if we try to use the $D$ in your question, we decrypt this as: $$D(16) = (7 \cdot 16 - 10) \mod{26} = 24$$ which is obviously not right. The issue is that your ...

6

W is 87 in ASCII, so $$87a+b\equiv064066\pmod{256256}.$$ I is 73 in ASCII, so $$73a+b\equiv158368\pmod{256256}.$$ Subtracting, you get $$14a\equiv-94302\equiv161954\pmod{256256}.$$ Unfortunately 14 is not coprime to 256256, so you'll need to use other letters to figure this out. Once you get an equation of the form $$ma\equiv n\pmod{256256}$$ you ...

5

You seem to have made a mistake in your arithmetic: $$108108 - 72097 = 36011 \ne 36012.$$ The number $36011$ is invertible modulo $256256$, and thus you can find $a$ and $b$ in a straightforward manner. More generally, you could end up in a situation where both the difference of the ciphertexts $d_c$ and the difference of the plaintexts $d_p$ might share ...

5

Well, to start off with, we have: $$k_1 m_1 + k_2 - n_1 p = c_1$$ $$k_1 m_2 + k_2 - n_2 p = c_2$$ $$k_1 m_3 + k_2 - n_3 p = c_3$$ Where we know $m_1, c_1, m_2, c_2, m_3, c_3$, and we don't know $k_1, k_2, p, n_1, n_2, n_3$. I chose to use explicit unknown integers $n_1, n_2, n_3$, rather than modulo an unknown $p$, as it makes it easier to justify the ...

4

OK, to understand this issue, let's first recap how the affine cipher is defined: $$c=a\cdot x+b\bmod m$$ Note that the following holds: $a\cdot x+b=c\iff a\cdot x=c-b$, where you would calculate $-b$ as $m-b$ which is $>0$ because $m>b$ because otherwise you could reduce $b\bmod m$ further. Ok, so on our way to decryption we now only need to get $x$...

3

This is a simple variant of the Vigenère cipher, and can be broken in basically the same way: First, you need to determine the key length. The standard methods for doing this for any Vigenère-like cipher, like Kasiski examination or calculating the index of coincidence, work just fine here. Once you've determined that the key most likely consists of $k$ ...

3

Multiplication by 2 modulo 26 is indeed not a permutation. For example, $$2 \times 13 = 26 \equiv 0 = 2 \times 0 \pmod{26}.$$ The necessary and sufficient criterion for the affine map $x \mapsto ax + b$ to be a permutation of the integers modulo $m$ is that the multiplicative constant $a$ and the modulus $m$ must be coprime; that is, their greatest common ...

3

This can easily be solved by brute force. Start with the following relationships: $$72097a + b = 24328 \pmod{256256}$$ $$108108a + b = 164193 \pmod{256256}$$ then rearrange to obtain two expressions for $b$ in terms of $a$: $$b_0 = 24328 - 72097a \pmod{256256}$$ $$b_1 = 164193 - 108108a \pmod{256256}$$ Now iterate through all the possible values of $a$ (...

3

The answer is 1 I think because if we apply a chosen plain text attack, then we need at least 2 encrypted alphabets and two plaintext alphabets corresponding to the related encrypted alphabets. Then we will have two variable and two equations. By solving those you can get the additive key as well as the multiplicative key.

3

$a\cdot x +b$ means affine not permutation. And $a\cdot x +b \bmod 26$ is modular affine transformation. $a\cdot x +b \bmod 26$ can have at most $26\cdot 26$ affine transformations some of which have no inverse and therefore without an inverse an affine transformation is not suitable for encryption where it is already not close to the modern encryption ...

2

Given that you have parts of the plain text and its corresponding ciphertext, this is called a known plaintext attack. Given an affine cipher that has a key that is composed of 2 parts $a$ and $b$, you can express it as a system of 2 equations with 2 unknown. Assuming the usual mapping $\mathtt{a} \to 0$, $\mathtt{b} \to 1$, etc., you need to solve the ...

2

If you want to find the multiplicative inverse of an integer a (mod n) you can use the extended Euclidean algorithm. For two integers a and b, the Extendend Euclidean Algorithm not only calculate the greatest common divisor d but also two integers x and y that satisfy the following equation: ax + by = d = gcd(a,b) (where gcd is the greatest common ...

2

While it's hard to prove that something has not been done, I'm fairly confident in asserting that affine ciphers (with $a \not\equiv \pm1$) are purely educational toys and have never been used for serious encryption (i.e. something not deliberately designed to be broken), except perhaps arguably as parts of a more complex cipher. For one thing, affine ...

2

If there was $x_1 \neq x_2$ in the ring of integers modulo $n$ such that $$ax_1+b \equiv a x_2+b \pmod n$$ subtracting the two sides would give $a(x_1-x_2) \mid n$ and since $\gcd(a,n)=1,$ this means $x_1 \equiv x_2 \pmod n$ implying the map is a permutation under this assumption.

2

There are several ways to break an affine cipher without any known plaintext. First of all, for the common case of $n = 26$, there are only $12$ possible values of $a$ (since $a$ and $n$ must be coprime) and $26$ possible values of $b$, for a total of $312$ possible keys. That's small enough that you can easily test all the keys and simply inspect the ...

2

Remember when you solved systems of linear equations in school? This is essentially the same. You just swap out $K=\mathbb R$ for $K=\mathbb F_{601}$ which allows you to essentially do the same things as with $\mathbb R$, even if it is a little bit less inttuitive. First too $\mathbb F_{601}$, as $p=601$ is prime, this is what is called a field. Essentially ...

2

The math goes: add the integer assigned to a, the integer assigned to z, and from that constant (which can be pre-computed) subtract the integer assigned to the letter to encode; that gives the integer assigned to the encoded letter. This works for a to z and encodings with consecurive letters of the alphabet assigned consecutive integer values (including ...

2

Assuming plaintext and ciphertext alphabets are $U=\{0,\ldots,25\}$, taken to be the ring of integers modulo 26, and the keyspace is $U^2$ with $$(a,b)\in U^2,$$ it is clear that for plaintext $x=2t$ corresponding to even numbers, $(a,b)$ and $(a+13,b)$ give the same $y$ violating the invertibility of the encryption. Moreover, if $b=0$ $a$ can't be zero for ...

2

When working with modulo arithmetic, in case of trouble, get back at what the notation used truly leans. When the question correctly derives $18\,a+0=12$, that really is a shorthand for $18\,a+0\equiv12\pmod{26}$. By definition of the equivalence..modulo notation, that is meaning $(18\,a+0)-12$ is divisible by $26$ when computing in (signed) integers $\... 1 No, you need to have a corresponding value for the letter$0$. Usual affine cipher schemes have the form$(a * x + b)modk$Let's say$a = 3$and$b = 6$. If we would encrypt the letter$g$:$(3 * 7 + 6)mod27 = 0$You wouldn't have a corresponding letter for the value$0$, since your alphabet starts at$1$. You could even get the same value ... 1 After$3a=-1 \pmod{26}$note that mod$26$we have$-1 = 25=51=3\cdot 17$, so$a=17$. Alternatively, note that$3\cdot9=27=1$so we can multiply both sides by$3^{-1}=9$and$-9=17\pmod{26}$. And then$5\cdot17 +b = 9$, and$5\cdot 17=85=7$and so$b=9$. Now substitute$p=3$in the encryption formula$c=17p+9$for the final question. 1 If I'm reading your question right, you've made two simple math mistakes: The solution to$-1 \equiv -15a \pmod{26}$isn't$a = 15$; it's$a \equiv 15^{-1} \pmod{26}$, or$a = 7$. I'm not sure where you got$b = 3$, but it's not correct, either. The right solution, using the correct value of$a = 7$, is$b = 19 - 2a = 19 - 14 = 5$. (FWIW, using the ... 1 Since this appears to be a homework exercise, I'll just give you a hint: write out the full expression for$e(e(e(x)))$. Note that the resulting expression will itself be an affine cipher, i.e. it can be written in the form $$e(e(e(x))) \equiv a'x + b' \pmod{26}$$ with some coefficients$a'$and$b'$that depend on the original values of$a$and$b$. Now, ... 1 You can simply extend your "alphabet", so you would perform calculations modulus 26 + 10 = 36. For instance, if you did encode 'A' to the value 0 and 'Z' to the value 25 then the digit '0' would become 26 and the digit '9' would become 35. You can of course also start with 0 and place the digits before the alphanumerical letters. Kind of obvious, but the ... 1 An encryption scheme is said to achieve perfect secrecy if for every probability distribution over M (the messsage space), every message m$\in$*M* and every ciphertext c$\in$C for which Pr[C = c]>0: Pr[M = m | C = c] = Pr[M = m] or, equivalently, Pr[E(K,m)=c]=Pr[E(K,m')=c] where E is the encryption algorithm that encrypt the message M according to the key ... 1 In general the key and ciphertext suffices, unless there are things missing such as an IV vector or other parameters. The trick is that you would still need to find the actual algorithm. Although Kerckhoffs principle does apply, that doesn't mean that you are always able to find the algorithm given such small amounts of input. If the algorithm is secret or ... 1 W = 87; I = 73; S = 83; K = 75 This yields the following system of equations:$\begin{cases} 87a+b \equiv 64066 \pmod {256256}\\ 73a+b \equiv 158368 \pmod {256256}\\ 83a+b \equiv 92525 \pmod {256256}\\ 75a+b \equiv 143358 \pmod {256256} \end{cases}$The following proposition is useful. Proposition If$x \equiv y \pmod {n}$then$x \equiv y \pmod {n/d}\$ ...

1

Your formulas are wrong. If $$c \equiv 7p + 11 \mod{27}$$ then by applying the modular arithmetic function $$c - 11 \equiv 7 p \mod{27}$$ and then $$(c - 11) \times 7^{-1} \equiv p \mod{27}$$. Therefore, the decryption function is: $$p \equiv (c - 11) \times 7^{-1} \mod{27}$$ For this we need to compute de multiplicative inverse of 7 modulo 27. Since ...

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