# Tag Info

4

Whether 2n − 1 is prime isn’t very important if we look for multiplication by certain constant in F2n . Multiplicative groups of finite fields are always cyclic, and any cyclic group has elements of the full order, prime or composite. As follows from inspection the code, mathematics of this example is iteration of a linear operator on 33-dimensional vector ...

3

Over a commutative ring $R$ a matrix $A$ is invertible iff $\det A$ is a unit: see Invertible matrices over a commutative ring and their determinants. In your case this means exactly $\gcd(\det A,n)=1$.

3

For the first one, find the equation of the line through the two given points: It is $y=1$. Find the three intersection between this line and the curve. Substituting in $y=1$ in the curve equation and simplifying gives $x^3-x=0$, with the three solutions $x=0$, $x=1$, and $x=-1$. (If the equation had been any harder, you could have simplified it by dividing ...

2

See Harald Hanche-Olsen for most of the solution. When the two points are the same, there are lots of lines through them. You need the line that is tangent to the curve at that point. Differentiate the equation to find the slope of the tangent $$2y\frac{dy}{dx}=3x^2+2x-1$$ and, oddly enough, the slope of the line $dy/dx$ is zero again, and the line is ...

2

You don't need a text on cryptography, these are elementary facts that you find on every elliptic curves text. For example, check J.Silverman's "The arithmetic of elliptic curves" or Washington's "Elliptic curves: number theory and cryptography".

2

One approach (see Example $15.5$ at Elliptic Curve Cryptography), is the following. Take $x = 0 \ldots 16$ and for each $x$ solve: $$y^2 = x^3 + 2x + 2 \pmod {17}$$ This yields the following sets of points: $x = 0, 7, 10, y = 6, 11$ $x = 3, 5, 9, y = 1, 16$ $x = 6, y = 3, 14$ $x = 13, y = 7, 10$ $x = 16, y = 4, 13$ You can use Hasse's Theorem to ...

2

You are nont soing anything wring in the calculation. It is just that the modulus and exponent are suboptimal for cryptographic purposes. While it is clear that $n=7\cdot 11$ must be composed of very small primes if one wants such an exercise to be feesible for manual calculation. But as direct consequence we'd have an immediate problem with the relatively ...

2

Careful! The elliptic curve is defined over a field $\mathbb F$, but is itself a group $G$. These are two completely different structures. If $(x,y)$ is a point on the elliptic curve (and therefore an element of $G$), then $x$ and $y$ are elements of the field $\mathbb F$. The "characteristic of the group" makes no sense; presumably you mean the ...

2

Right, it doesn't quite work the way you did it. This is because you'd want to calculate the inverse of $k$, but not mod $p$. You'd actually want to look at $\phi(p) = p-1$, and calculate the inverse of $k$, mod $(p-1)$. (Here $\phi$ is the Euler phi-function.) Note that in your example, this is actually impossible, since $2$ is not invertible mod $6$ ...

1

Usually we consider real-valued random variables, but there's no problem at all in allowing $\mathcal M$-valued ones, especially if if $\mathcal M$ is a discrete space. We could, if we wanted to be pedantic, encode messages by real numbers. EDIT: For a more general definition of random variables, see e.g. Wikipedia.

1

In general, when $A,B$ are the roots of $x^2 + ax + b = 0$, we know that $(x-A)(x-B) = x^2 + ax + b$, and so $x^2 - (A+B)x + AB = x^2 + ax + b$ (for all $x$), so that $a = -(A + B), b = AB$, or $A+B = -a, AB = b$. So the coefficients of the quadratic are just the negative sum of the roots, and their product respectively. When $n = pq$, we know that ...

1

Let $\mathcal{K}$ be your pairs of known ciphertexts and plaintexts (the ~1% you mention in your question). You know $N$ and $e$ and receive $C = M^e$. You want to compute $M$. Algorithm: If $(C,\color{gray}{M}) \in \mathcal{K}$, decode to $M$. Else, pick an arbitrary $(C_1,M_1) \in \mathcal{K}$ and compute C_2 = C_1 C = M_1^e M^e = (M_1 M)^e ...

1

Sure. Create a computer system where students can enter a password of their choice and then donate as much money as they choose. If there is not enough total money at the end, students simply re-enter their passwords and the machine gives back that much money.

1

There are formulae for these operations: http://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication. Simply fill in the formulae to get the answers.

1

There are two reasons they are discrete. First, they operate on natural numbers, not reals, so they are by nature discrete. Second, you would like an adversary not to learn anything about $f(n)$ from $f(n-1)$ so they have to be very discontinuous

1

The purpose of a trapdoor function means it has to be discrete. After all, the purpose is that it will be done by computer. The typical ways you can talk about continuous functions and computability are largely irrelevant here - that is, saying that $f$ is computable if, given an oracle outputting digits of $x$ (or other equivalent formulation), it is ...

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