# Tag Info

21

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation $$\varphi^2-t\varphi+q = 0 \qquad\in\... 19 Can someone explain why is that the case? Cryptosystems based on finite sets have two very nice properties: There is an upper bound to the size of all involved mathematical objects. This also allows one to predict things like memory usage rather well. This also means that the precision / memory you need can't grow arbitrarily / infinitely. You can actually ... 16 This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup H of group G divides the order of G. Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, ... 15 A safe prime is a prime number p for which (p-1)/2 is also prime. The order of an element g of the group \mathbf{Z}^*_p (the integers modulo p, excluding 0) is the smallest integer n such that g^n\equiv 1\pmod{p}; this is always a factor of p-1. The orders of the subgroups of the group generated by g are the factors of the order of g; ... 15 I'll use these common definitions and notations: a\equiv b\pmod c means that c>0 and c divides b-a a\equiv b^{-1}\pmod{c} means that a\cdot b\equiv 1\pmod{c} a=b\bmod c means that a\equiv b\pmod{c} and 0\le a<c a=b^{-1}\bmod c means that a\equiv b^{-1}\pmod c and 0\le a<c \varphi is the Euler totient function (also noted \... 14 Ok, I will start with a cryptographic bilinear map. Cryptographic Bilinear Map A cryptographic bilinear map e: G_1\times G_2 \rightarrow G_T as the name says is a map that is linear in both components, i.e., it holds that for all g\in G_1 and h\in G_2 and all a,b\in Z_p (where p is the order of all groups) we have that e(g^a,h^b)=e(g,h)^{ab}. ... 14 Mostly, I would say that finite groups get used in crypto because they're a good way to describe things that naturally appear in many crypto schemes. For example, going way back to the early days of cryptography, consider the simple Caesar cipher, where you replace every letter with the one n positions after it in the alphabet, wrapping around from Z back ... 13 The cornerstone of the argument is the following: If the cycle attack works, then you can factor n (see details below). The attacker can choose e. I.e., when trying to factor n, the attacker is not constrained to use the specific e which you selected for your public key; he can invent his own e, since he will do all the computations himself. ... 12 Note that you do not have an efficiently computable homomorphism from G_1 to G_2, but in Type-2 you have an efficiently computable homomorphism \psi: G_2 \rightarrow G_1 and in Type-3 you do not have one. But what I don't understand is what is the use of the homomorphism in cryptography? Well, if you have a tuple (aP',bP',cP')\in G_2^3 with P' ... 12 It depends. If the order m of g's group is known and a has an inverse modulo m (which is the case if and only if a is coprime to m), then it is easy: Calculate the inverse b:=a^{-1}\bmod m (for instance, using the Euclidean algorithm), and compute the power (g^a)^b. By Lagrange's theorem, this equals g. However, there are cases for which ... 11 I’m trying to understand which properties of a group are used in DHKE at each step. Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (so A^3 = A\times A \times A = (A \times A) \times A = A \times (A \times A) is well defined), but other than that, you really don't need anything. You don't ... 10 The question makes a number of statements that are incorrect. It is not correct that a fixed point is guaranteed to exist. It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist. Moreover, the existence of fixed points has only an extremely tenuous connection to security. Assume E is a ... 10 Question: Given n values v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p for a large n can the adversary learn the value \alpha? Answer: assuming that the r_i values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about \alpha (other than whether or not it's 0). We can see ... 10 Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime order subgroup. In (a little) more detail: Elliptic-curve cryptography is mostly based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). That means ... 9 The security of \varphi and \lambda should be equivalent since they are mathematically equivalent in the context in which they are used. (That is: the d´th power in (\mathbb Z/pq \mathbb Z)^\times is exactly the same operation as the dth power.) However, the mathematically right modulus for computing d is \lambda(pq): it is precisely the ... 9 A possible analogy is two layers in a communication protocol, with p and n the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically due to overhead added by the upper layer, reducing its maximum packet payload compared that of the lower layer). We use limit p or n depending on if we deal ... 8 Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group Z_n with addition and let g be a ... 8 I'll add something to the previous answer. The first way to construct multilinear maps is pretty recent and was introduced by Sanjam Garg, Craig Gentry and Shai Halevi. What we want is given groups G_1,\ldots,G_n and G_T a map:$$e:G_1\times\cdots\times G_n\to G_T that satisfies the linearity property in DrLecter's answer. It's worth nothing here, ...

8

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{GF}(p^n)$, but they are constructed differently. For $n\ge2$, they are commonly called extension fields (as opposed to prime fields for $n=1$), as they can be ...

8

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography. Why not use singular curves? It turns out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm ...

7

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can ...

7

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...

7

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$. Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$. In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so: Interpret $x$ as a $k$ bit number, i.e. $x = ... 7 The best algorithm for computing discrete logs in a well-chosen finite field$\mathbb Z/p\mathbb Z$, where the safe prime$p$has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short. The GNFS costs$L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$bit operations, where$L = e^{n^{1/...

7

Integer operations as implemented on computers are isomorphic to a theoretical definition of integers. Otherwise operations would not give the correct results. Given the terminology in your question, I suspect that when you think of integer operations on a computer, you're thinking of operations on machine words. Cryptography uses numbers that don't fit in ...

6

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup. One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in $... 6 If$\mathcal{G}$is of order$N$(who doesn't look like a prime number btw) and$g$is a generator of$\mathcal{G}$then$g$has order N. Since$(g^{nq})^p=1$and$\forall 1\le k <p, (g^{nq})^k\neq 1$(g has order$N$and$knq<N$) then$g^{nq}$generates a subgroup of$\mathcal{G}$of order$p$and there's only one such subgroup :$\mathcal{G_p}$. The ... 6 Your first two paragraphs made a series of statements; these statements were less than perfectly accurate, and D.W. attempted to address those. You then went on and asked What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, ... 6 One way to do this, if you're working with a multiplicative group$Z^*_p$, is to pick a prime$p$so that$p-1$has a large prime factor$q$; once you have this, then to generate a generator of order$q$, you pick a random value$h$, compute$g = h^{(p-1)/q}$, and if that is not 1, then$g\$ is a generator of your group. Obvious questions: How do you find a ...

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