We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

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 ...

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/... 6 As said in the comments above, you have that$x \cdot x^{-1} = 1 \mod n $. Another way to say that is$k \times n=(x \cdot x^{-1}) -1$So no, you can't always find the exact value$n$from$x$and$x^{-1}$. Take$x=12 \ $and$x^{-1}=17$. You have$x \cdot x^{-1} = 204$. So$n$is a divisor of$204-1=203$, meaning,$ n \in \{29,203\}$(other divisors are ... 4 If $$x \times \frac{1}{x} = 1$$ then $$g^{x\frac{1}{x}} = g^1 = g$$ Alternatively, you could denote$\frac{1}{x}$as$x^{-1}$. In the context of cryptography,$\frac{1}{x}$will usually mean the modular multiplicative inverse of$x$, because cryptography usually works with modular arithmetic. With modular arithmetic, the way to evaluate the division ... 4 How is this done efficiently on the fly for Diffie Hellman? For Finite-Field Diffie-Hellman, you usually pick$p$such that$q=(p-1)/2$is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is$p-1=2q$. This leaves us with four divisors:$1,2,q,2q$. Once you know that, you can simply test that your ... 4 Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If$G \simeq H$via$\phi : G \rightarrow H$and$\phi$is computable, then indeed, DLOG is no harder in$G$than in$H$because you can transform the instance. In the case you mentioned, we have$G = \mathbb Z/(p-1) \mathbb Z$and$H = (\mathbb Z/p\mathbb Z)^\...

3

How many such Caley XOR tables are theoretically possible that hold such qualities for a 16*16 table? It is essential to define what we want to count. I read the constraints as A table of $r$ line and columns for an internal law $\boxplus$ on $\Bbb Z_r$ (the non-negative integers less than $r$), with line and columns in the same arbitrary order. More ...

3

TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem. How can we effectively compute the square root of an element in a group? One case where we can compute a square root is when the group order is known and it is odd. Any element $g$ in a ...

3

It's the size of the prime number of the underlying field in G1, G2 and GT. In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$. Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note ...

3

In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k$, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$? The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term ...

3

The additive inverse of $x$ is defined to be the value $y$ such the group operation $x + y$ results in 0. If we examine $\mathbb{Z}/7$, we find that every element there does have an additive inverse. For example, for the element 2, we find the additive inverse to be 5, as $2 + 5 = 0$ (computed modulo 7). You might be interested to learn that ...

2

By this definition is there any known algorithm based which one can compare the order of two random elements of the group $P_1$ and $P_2$? No, such an algorithm would allow for an easy break of the elliptic curve discrete logarithm problem. But as this problem is assumed hard for secure curves like secp256k1 us knowing such an algorithm is impossible. To ...

2

The multiplicative group $\mathbb{F}_{2^n}^{\ast}$ (which is cyclic) is used in defining LFSR sequences and nonlinearly filtered sequences typically as building blocks of stream ciphers. This group is part of the picture for block ciphers; most prominently, the field $\mathbb{F}_{2^n}$ is used (for $n=8$) for defining the AES. Boolean functions and vector ...

2

There are many different flavors of elliptic curves and coordinate systems for them with different costs for computing addition or scalar multiplication. You can find cost estimates for many of these at the Explicit-Formulas Database (EFD), and measurements from SUPERCOP at https://bench.cr.yp.to/. Certain curves like Curve25519 in Montgomery form $y^2 = x^... 2 What you are asking is in some sense a tautology. In any group$G$, Abelian or not, the subgroup generated by an element$g \in G$is Abelian. (Recall: the subgroup generated by$g$is:$ \langle g\rangle := \{g^0, g^1, g^2....\} $). Hence, you can probably take your favourite DLP-based encryption scheme and implement it in$G$, without dealing with the ... 2 No, this is a known variation of the computational Diffie-Hellman problem, called Inverse computational Diffie-Hellman (InvCDH), according to which on input$g$,$g^{x}$, it is difficult to find$g^{x^{-1}}$. See section 2.2 at Variations of Diffie-Hellman Problem by Bao et al. for more info and problem reduction proofs. 2 SHA256(SHA256(x)) Would this be a bijective mapping? or Surjective mapping? SHA-256 is almost certainly not injective on 256-bit inputs, so it is almost certainly not a bijection or a surjection onto 256-bit outputs either. And if SHA-256 is not injective, then applying it twice can't be injective—if$x \ne x'$are distinct preimages of$h$under SHA-... 2 First of all, note that, SHA-256 operates on a minimum of 512-bit messages. The message is always padded to be a multiple of 512-bit ( see padding below). For double SHA256(SHA256(m)), after the first hash, the result is padded to 512-bit. padding: The SHA-256 message format |L|1|0..0|message size in 64 bits|. L is the original message bits to be hashed, it ... 2 Yes, such a group is useful. In particular, when$N= p\cdot q$where$p,q$are both strong primes (i.e.$p=2p'+1,q=2q'+1$where$p',q'$are also prime numbers). Discrete logarithm in the prime order cyclic groups (order-$p'$and order-$q'$) is believed to be hard. Such a group is called a group with hidden order. A few examples of application: Fujisaki ... 1 I suppose it is a short Weierstrass curve. There are several possibilities: Projective coordinates: a point$P = (x,y)$is stored with three coordinates,$X$,$Y$and$Z$that satisfy$x=X/Z$and$y=Y/Z$. We note$P=(X:Y:Z)$. That means a point can have more than one representation (it is the same as fractions,$\frac 3 4$is the same as$\frac{15}{20}$). ... 1 The prototypical example of a group in cryptography is a cyclic group. You can write this in a variety of ways, so I'll go through a few quickly. Additively: Consider the group$\mathbb{Z}/n\mathbb{Z}$under$+$. This forms a group, and it's a cyclic group generated by$\langle 1\rangle$(subject to the relation that$n\cdot 1 = 0$). Note that the "... 1 Try doing some examples. Sage (free and open source software) is very helpful here. I think the simplest example is$E : y^2 = x^3 + 1$over$\mathbf{F}_5$. This curve has embedding degree$k=2$. sage: q = 5 sage: k = 2 sage: F.<z> = GF(5^2, modulus = x^2 + 2) sage: E0 = EllipticCurve(GF(5), [0,1]) sage: E = EllipticCurve(F, [0,1]) sage: E0 Elliptic ... 1 In a generic group, I don't know if it exists really a generic algorithm to solve your problem, but if you group is also a field ($\mathbb{Z}_p$with$p$a prime number for example), then you can use the Berlekamp algorithm to factorize$X^2 -x$where$x$is your element. I made an error, I've deleted the wrong part. 1 Well this answer is a bit of a fishing game, but I have a few leads after some thought and maybe they will help. The binary operation $$a*b = \underbrace{a^{a^{a^{\dots}}}}$$ where the chain is repeated b times, has been studied before. If this is what you mean by "Self-Power Map," then Tetration (and the associated hyperoperations) have been studied for ... 1 First of all, the idea of proving element equality does not make much sense, since that would reveal the secret element.$prove(X == T)$with secret$X \in G_1$and public constant$T \in G_1$reveals the value of$X$. What I was looking for instead is$prove(g_1^x == T)$with public constants$g_1, T \in G_1$and secret scalar$x$. It tuned out that type 2.... 1 Since$\gcd(2,467)=1$, one can observe using Fermat's little theorem that$4^{233}\pmod{467}=2^{466}\pmod{467}=1$. Thus, $$g^{a_1}=4^{400}=4^{233+167}\equiv\underbrace{1\cdot4^{167}}_{=g^{a_2}}\pmod{467}=89.$$ This results into identical session keys (shared secrets)$S=(g^a)^b=89^{134}\equiv161\pmod{467}$. 1 My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, group_order]. Actually, that's not the case - the point multiplication$xG$is well-defined for all integer values of$x$. While it could accept larger values since$(n+x)G=xG$, it would be wasteful computationally so I'... 1 Is that the best/fastest way to go? Well, unless you give some criteria, whether it's the best is unanswerable. However, it might not be the fastest; you could just note that$k = f_2 \cdot f_3 \cdot … \cdot f_i$and skip the baby-step-giant-step algorithm entirely. In addition, if all you want is a random element of the subgroup, you don't need to find a ... 1 A somewhat generic answer, given the question is quite generic. In cryptography, groups are usually chosen such that they have no large subgroups or other substructures which would speed up attacks. This also impacts computation speed, in the sense that group operations cannot necessarily be implemented to run faster, by use of such substructures. And a ... 1 is each element a generator here? if not why? Take the$2$and calculate$2 \cdot 2 \cdot 2 \equiv 8 \equiv 1 \mod7$. Therefore, not every element is a generator. is an element considered as generator only if$Order(G) = Order(g)$i.e$Order(g) = 6$hence$g=3$is a generator. A generator must generate all the element. If the order of$Order(a)...

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