New answers tagged

0

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


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


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


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}}$$


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


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


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

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


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


0

It's hard to answer given that there is no quantum computer to perform benchmark on. However, let us assume a quantum computer which would perform quantum operations as efficiently as our current standard computer can perform classical operations (this might be a bit unrealistic but it's hard to come out with realistic assumptions regarding quantum computing ...


0

Window size(w) depends on the NIST curve and the algorithm that you are going to use for point multiplication. I suggest you to look to the paper from Brown et al. Software Implementation of the NIST Elliptic Curves Over Prime Fields. They provide the number of operations in algorithms w. r. t. changing window size for some point multiplication algorithms. ...


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


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


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


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


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



Top 50 recent answers are included