# Tag Info

Let $a_p$ be a square root of $a$ modulo $p$, and let $a_q$ be a square root of $a$ modulo $q$. The four square roots are given by numbers $x,y,z,w$ such that: $x \equiv a_p \pmod{p}$ and $x \equiv a_q \pmod{q}$. $y \equiv a_p \pmod{p}$ and $y \equiv -a_q \pmod{q}$. $z \equiv -a_p \pmod{p}$ and $z \equiv a_q \pmod{q}$. $w \equiv -a_p \pmod{p}$ and $w ... 3 The four solutions are of the shape$x\equiv \pm b\pmod{pq}$and$x\equiv \pm c\pmod{pq}$. There are only two solutions modulo$p$. So$b\equiv \pm c\pmod{p}$. It follows that either$b-c\equiv 0\pmod{p}$or$b+c\equiv 0\pmod{p}$. Thus one of$\gcd(m,b-c)$or$\gcd(m,b+c)$is equal to$p$, and the other is equal to$q$. The gcd can be computed cheaply ... 3 So, we are looking for a generator of$\mathbb{F}_{125}^*$, where$\mathbb{F}_{125}\simeq \mathbb{F}_5[x]/(x^3+x+1)$. Since the group$\mathbb{F}_{125}^*$has$124=2^2\cdot 31$elements,$g\in\mathbb{F}_{125}^*$is a generator iff: $$g^{\frac{124}{2}}=g^{62}\neq 1,\qquad g^{\frac{124}{31}}=g^4\neq 1.$$ How to get a suitable candidate? Just take a random ... 2 Hint: company B uses the same modulus with three different public exponents. That means that the attacker has access to: $$C_1 \equiv M^{17} \pmod{9997}$$ $$C_2 \equiv M^{19} \pmod{9997}$$ $$C_3 \equiv M^{21} \pmod{9997}$$ More importantly, for any (possibly negative) integers$k_1$and$k_2$we have: $$C_1^{k_1} \equiv \left ( M^{17} \right )^{k_1} ... 2 To find all the primitive elements you really need to find just one. Indeed, let g be any primitive element modulo p. Then all other primitive elements have form g^a where a is coprime with \phi(p-1). The key in DF key exchange schema is k=g^{ab}, so k = m^b = n^a hence it is in \langle m \rangle (because it is k=m^b) and similarly it is ... 1 If it is unchanged by the private key, then surely it is also unchanged by the public key (and vice versa). Thus, you must find the number of solutions to m^3=m\pmod{N}. This amounts to solving two different equations m^3=m\pmod{p} and m^3=m\pmod{q} and combining them using the Chinese remainder theorem. In each case, m=0 is a solution, and also ... 1 Hint \ We can split \rm n>1\, into nontrivial factors by a quick gcd calculation if we are given a nonzero polynomial having more roots \,r_i\, mod \rm\, n\, than its degree. Namely, one of \,\gcd(n,\,r_i-r_j),\ i\neq j\, yields a proper factor of \,n.\, See here for details. 1 This is a very nice question that feels like it should be obvious, but which isn't (or at least wasn't to me). I blame it on the phrasing "at least four". When you figure out the nine messages, three of them are trivially 0, -1, 1. When you have four, you have to have at least one nontrivial message. It turns out this is the key. [Originally I thought I ... 1 For 1, you need to verify that A is invertible. The easiest way is to check the determinant. That will mean you can decrypt the message. Do you see why? For 2, you just pad the message with something to make enough characters. For example purposes, you often use X, so the last block would be AX. If you imagine adding one X (or, for some other codes, ... 1 While your observation is right, i.e., the recipient can be confident that the private key (s,m) was used to encrypt x_i\to y_i by using the public key to decrypt y_i\to z_i and check whether x_i=z_i, the actual procedure is somewhat different. First of all, the "signature" of the message won't be an encrypted version of the full message (which woul ... 1 Because we (as decrypters) know that 55=5\times 11, we also know that Carmichael's function \lambda(55) =\text{lcm}(\phi(5), \phi(11)) = \text{lcm}(4,10) = 20 So we need to find the multiplicative inverse of 3 \bmod 20, that number b such that 3b \equiv 1 \bmod 20, which is obvious enough by inspection for these small numbers (3\times 7 = 21) ... 1 You can see here https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture3.pdf for lecture notes which explain the whole procedure. It is a lengthy process. I will explain briefly here. First you divide the 64 bits into left and right part, both 32 bits. The right part 101010...1010 (32 bits) is then extended into 48 bits by the following method: ... 1 Depending on how cryptography heavy/math heavy the resulting paper is supposed to be you might want to include theory relating to attacks on curves. This would be weil-tate pairing and possibly the background needed for the weil-descent attack. Who is supposed to be the target audience of the paper? Is this a math paper for academic cryptographers? Or more a ... 1 The short answer to your question is that, yes, you would have to apply a different transformation in your second example, but that, in that particular example, you would not always be able to determine with which of the two states the system had been in. The reason for the latter is that the two state vectors in the second example are not orthogonal, so no ... 1 Using CRT,$$m^e \equiv m \pmod p \\ m^e \equiv m \pmod q$$Mod p: Either$$m \equiv 0 \pmod{p}$$or$$e \log m \equiv \log m \pmod{p-1} \iff \\ (e - 1) \log m \equiv 0 \pmod{p-1}$$Now count the number of values of$\log m$.$\log m$is any multiple of$\frac{p-1}{\gcd(e-1,p-1)}$. The number of multiples is$\gcd(e-1,p-1)$. Same story mod q. So it's ... 1 Searching for curves of the form$y^2=x^3+x+k$gave me the following hit. With$k=6$, the value of$f(x)=x^3+x+6$is zero for$x=6$(1 point), and$f(x)$is a non-zero square of$\Bbb{F}_{19}$for eight choices$x=0,2,3,4,10,12,14,18\$ (16 points). Including the point at infinity gives us a total of 18 points. The Mathematica snippet counter = 1; For[y = ...