Hot answers tagged

17

By the same argument, they would have to forbid $d = 1234$; after all, an attacker can trivially compute the value of $1234 G$; and if they see it, then they can immediately infer $d$ without having to complete a discrete log over an elliptic curve. Of course, this logic would forbid all possible values of $d$... The issue is that if the attacker gets ...


11

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


7

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST. As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography ...


5

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log(N^2) = 2 \log(N)$. So 4096 for 2048-bit RSA, double that for 4096-bit. This paper (pdf) has an algorithm using $2n+3$ qubits, where $n=\log N$. How many qubits are required to break ...


4

What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe or Post Quantum Cryptographic algorithm. However there is an true Post Quantum Key Exchange algorithm which uses ...


3

On standard way to compute scalar multiplication is to use Double-and-add algorithm: The idea is to take the binary representation of your scalar $b = b_0 ... b_m$in your case $b = 3$ gives $b_0b_1 = 11$. First you initialize your result $Q$ with $0$. Then for each increasing bit index $i$, you set $Q = 2Q$ (computed with the doubling formula) and if ...


3

Well, let's start from the beginning then. The string "Hi" is actually encoded as {0x48,0x69} (as per the ASCII table), so a string-number array conversion is as simple as a bunch of table look-ups. Now converting between hexadecimal and binary and back is easy. Just note that each hexadecimal character corresponds to exactly four bits in binary (because ...


3

Generally speaking, there are (at least) three reasons to put a KDF in between an DH shared secret and the bulk encryption. Improved re-usability. If you don't post-process the shared secret with a KDF there's no way to give the sender and the recipient different keys for each direction or to split up authentication and encryption keys. An additional bonus ...


2

The paper states $R$ contains $2^{255}x^{10}-19$, which represents $0$ in $\mathbb Z/(2^{255}-19)$. In other (slightly simplified) words: $$x^{10} \;\;\text{is}\;\; 2^{-255}\cdot19 \text!$$ (Note that this contradicts your comment to the question: $x^{10}$ does not represent $2^{255}$.) To understand this, recall that a value in $\mathbb ...


2

It's not harder. Solve the DL problem to get $x$ in $Q=x.P$. $Q = \sum_{i=1}^{n} x_i.P = (\sum_{i=1}^{n} x_i).P= x.P$ => any set of $x_i$ that sums to $x$ (modulo the group order) is a solution to ECFP.


2

The fact is that the discrete logarithm problem (DLP) is solved using different algorithms in the cases of multiplicative groups (where normal DH applies) and elliptic curves (where ECDH applies). The behavior of these algorithms is quite different. For multiplicative groups, where the NFS for logarithm is used, a huge part of the computation depends only ...


2

Given two points $P_1 = (x_1,y_1)$ and $P_2 = (x_2, y_2)$ on an elliptic curve $y^2 = x^3 + ax +b$, the sum $P_3$ of $P_1$ and $P_2$ is $P_3 = P_1 + P_2 = (x_3,y_3)$ where $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = y_1 + \lambda(x_3 - x_1)$ where $\lambda = (y_1 - y_2)/(x_1 - x_2)$ if $P_1 \neq P_2$ and $\lambda = (3x_1^2 + a)/(2y_1)$ if $P_1 = P_2$. The ...


1

ECDH is included in the ciphersuites, so the only answer is: yes, this should be possible. For your further research, it might help to know that Crypto.SE features a lot of Q&As related to “OpenSSL ECDH”. Also see the related documentation at the OpenSSL wiki for practical code examples showing how to use ECDH in OpenSSL, how to use the low-level APIs ...


1

Using $x$-coordinates only, given a point $G = (x_0,y_0)$ on an elliptic curve $y^2 = x^3 + ax + b$ and a scalar $r$, the Montgomery ladder outputs the $x$-coordinate of $rG$. However, a closer look at the algorithm shows that the other accumulator used in the computation contains the $x$-coordinate of $(r+1)G$. Letting $x_1$ the $x$-coordinate of $rG$ and ...


1

Let $j_w$ be the root of Weber polynomial $W_D(X)$ over $F_p$, then the root $(j_h)$ of Hilbert polynomial $H_D(X)$ over $F_p$ is given by $$j_h=\frac{{(j_w^{24}-16)}^3}{{j_w}^{24}}$$


1

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-exponential attack to compute isogenies on SUPERSINGULAR elliptic curves. The cryptosystem proposed by DeFeo, Jao, and Plut back in 2011 is based on Supersingular ...



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