Lời mở đầu

Tháng 3 năm 2016, Bộ Ngoại Giao Hoa Kỳ, đứng đầu là bộ trưởng John , đã dẫn một đoàn đại biểu tới các nước ASEAN trong đó có Việt Nam để thảo luận về phát triển Fintech và đặc biệt là về công nghệ Blockchain. Tháng 9 năm 2015, Ủy ban giao dịch hàng hóa tương lai Mỹ công bố, Bitcoin đã chính thức được đưa vào danh sách hàng hóa được phép giao dịch tại Mỹ. Công nghệ Blockchain và Bitcoin là công nghệ tiền số ra đời năm 2009 và ngày càng có nhiều quốc gia và các tổ , doanh nghiệp cho phép lưu hành và thanh toán bằng loại tiền số này trong không gian mạng Internet toàn cầu. Tháng 4-2016, giá trị thương mại của Bitcoin đã lên đến 6.5 tỷ USD. Nền tảng cơ sở của Bitcoin chính là lý thuyết về mật mã mà cụ thể ở đây là hàm băm và lý thuyết về chữ ký số dựa trên Hệ thống đường cong Elliptic (ECC).

Bên cạnh việc sử dụng trong tiền số , ECC còn được ứng dụng rất nhiều trong thực tiễn ngành Công nghệ thông tin. Các trang Web bảo mật https (http-secure) thường được dùng trong thanh toán điện tử hay ứng dụng riêng tư như gmail đều sử dụng các giao thức TLS (Transport Layer Security) mà trước đó là SSL (Secure Socket Layer). Trong các giao thức này ECC được sử dụng để trao đổi khóa phiên. Các giao dịch remote access được sử dụng rất nhiều trong thế giới UNIX, LINUX là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa. Ưu điểm của hệ mật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ (160 bit tương đương với khóa độ dài 1024 bit trong hệ mật RSA), do sử dụng độ dài khóa nhỏ nên tài nguyên phục vụ cho ECC thường nhỏ hơn rất , bên cạnh đó hiệu năng tính toán cũng được nâng cao rõ rệt. Hiện nay ECC đang là xu thế để thay thế RSA.

Cơ sở toán học của hệ mật ECC là nhóm giao hoán Abel các điềm nằm trên đường cong Elliptic. Ngoài việc đường cong Elliptic là cơ sở cho hệ mật ECC, hệ mật ID-, đường cong Elliptic (EC) còn là công cụ hữu hiệu để phân tích số nguyên ra thừa số nguyên tố, hoặc dùng để kiểm tra tính nguyên tố của số . EC cũng là cơ sở để chứng minh định lý Fermat nổi tiếng đã tồn tại nhiều trăm năm qua.
Đường cong Elliptic là một trường hợp đặc biệt của phương trình Diophant. Lý thuyết về đường cong Elliptic (EC) rất phong phú và độ sộ. Trong cuôn sách “Elliptic Curves Diophantine Analysic”, tác giả Serge Lang đã phát biểu về phương diện học thuật: “Có thể viết vô tận về đường cong “. Các lý thuyết và khái niệm liên quan tới EC có thể liệt kê một số như dưới đây:
Lý thuyết nhóm, vành, trường trong đại số trừu
Đa tạp Affine, đa tạp Jacobian và đa tạp xạ ảnh trong hình học đại số
Điểm Torison, Divisor, cặp song tuyến tính Weil, Tate - Lichtenbaum
Lý thuyết trường Galois, tự đồng cấu- ánh xạ Frobenius
Lý thuyết Baker-Feldman, Baker-Tijdeman và lý thuyết Kummer
Số p-adic, Isogenies, hàm Sigma và hàm Zeta
Nhóm đối đồng điều, đối đồng điều Galois và đối đồng điều phi giao hoán (Topo đại số)
Nhóm Mordell-Weil, Selmer và nhóm Shafaverich-Tate
Phương pháp hình học và Tựa tuyến tính (Quasilinear)

Với ý nghĩa to lớn về cả thực tiễn và học thuật, EC là nền tảng toán học quan trọng trong đại số hiện đại cũng như lý thuyết mật mã hiện tại. EC cũng là nền tảng quan trọng trong chính phủ điện tử và thường mại điện . Chính vì những điều này mà Chuyên đề “Hệ mật mã khóa công khai dựa trên đường cong Elliptic” được lựa chọn để trình bày báo cáo.

Với khối lượng kiến thức và khái niệm đồ sộ như đã liệt kê ở trên việc nghiên cứu và đào sâu về đường cong Elliptic gặp không ít khó khăn cho những người làm Công nghệ thông tin (CNTT) mà toán học không phải là chuyên môn chính. Mục tiêu của chuyên đề này là tổng hợp những khái niệm và kiến thức cơ bản nhất của EC liên quan đến cơ sở toán học của Hệ mật dựa trên đường cong Elliptic. Đồng thời người viết cũng chứng minh lại một số định lý và bổ đề theo cách dễ hiểu hơn, tránh dùng đến các khái niệm quá phức tạp và xa lạ với chuyên nghành CNTT…

Phạm vi của chuyên đề cũng được giới hạn với những khái niệm và lý thuyết đủ cho các ứng dụng cơ bản của EC, các phát triển của EC thành hệ mật ID-based, hoặc các ứng dụng cơ bản của EC, các phát triển của EC thành hệ mật ID-based, hoặc các ứng dụng về chữ ký số tập thể, chữ ký số nhóm, chữ kỹ ngưỡng, chữ ký ủy nhiệm, chữ ký số mù sẽ không được đề cập đến trong khuôn khổ của báo cáo này.

Báo cáo chuyên đề được kết cấu thành 02 chương, chương 1 trình bày các khái niệm, định nghĩa cơ bản về đường cong Elliptic (Phương trình của EC, nhóm cộng Abel các điểm trên đường cong, chứng minh định lý về nhóm…). Chương 2 trình bày về Hệ mật dựa trên đường cong Elliptic và một số ứng dụng trong mã hóa, xác thực chữ ký số, trao đổi khóa dựa trên bài toán khó Logarithm rời rạc.

… To be continued

Toàn bộ nội dung trên đây được trích từ chuyên đề: “Hệ mật mã khóa công khai dựa trên đường cong Elliptic - Tổng quan về hệ mật mã khóa công khai” của tác giả Đăng Minh Tuấn - Trong tạp chí Epsilon - Số 09 - Tháng 06/2016

P/s: Những phần tiếp theo trong bài báo này khá cao cấp, nên mình tạm dừng ở đây, vào có dịp sẽ quay lại

Link pdf: Tại đây

ELLIPTIC CURVE

OVERVIEW

The use of elliptic curves for public-key cryptography was first suggested in 1985. After resisting decades of attacks, they started to see widespread use from around 2005, providing several benefits over previous public-key cryptosystems such as RSA.

Smaller EC keys offer greater strength, with a 256-bit EC key having the same security level as a 3072-but RSA key. Furthermore, several operations using those keys( including signing) can be more efficient both time- and memory-wise. Finally, since ECC is more complex than RSA, it has the welcome effect of encouraging developers to make use of trusted libraries rather than rolling their own.

This course is aimed to give you an intuition for the trapdoor function behind ECC ; dip your toes into the mathematical structure underlying it; and have you breaking popular schemes like ECDSA.

Background Reading

Elliptic Curve Cryptography (ECC) is an asymmetric cryptographic protocol that, like RSA and Diffie-Hellman (DH), relies on a trapdoor function. To recap: trapdoor function allow a client to keep data secret by performing a mathematical operation which is computationally easy to do, but currently understood to be very expensive to undo.

For RSA, the trapdoor function relies on the hardness of factoring large numbers . For Diffie-Hellman, the trapdoor relies on the hardness of the discrete log problem. For both RSA and DH, the operations that run through the veins of the protocol are familiar to us. Multiplying numbers and taking powers of number are things we are taught to do in school. ECC stands out, because the group operation in ECC won’t pop up in your life unless you are looking for it.

Note: This discussion here will not be total, and those who are really looking to understand ECC, I recommend these notes Elliptic Curve notes by Ben Lynn, and the textbook “An Introduction to Mathematical Cryptography”, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman.

Let’s start thinking anout ECC by looking at what we mean by an elliptic curve. We will be studying Weierstrass equations, which are of the form $Y^2 = X^3+aX+b$

Elliptic curves have an amazing feature: We can define an operation that we will call “point addtion”. This operation takes two point on some curve and produces a third point on the curve. Taking the set of points on an elliptic curve, point addition defines an Abelian group operation.

Note: There’s a lot of text here. Let’s motivate this ! We can understand scalar multiplication of a point as the repeated point addtion of the same point. $Q=2P=P+P$. It turns out that scalar multiplication is a trapdoor function ! ECC relies on the hardness of finding the $n$ such that $Q=nP$ given Q and P.

So how do we understand point addtion ?

Geometrically, we can understand point addtion $P+Q$ like so. Take an elliptic curve and mark the two points $P,Q$ along the curve with their $x,y$ coordinates. Draw a straight line that passes through both points. Now continue the line until it intersects your curve a third time. Make this new intersection $R$. Finally, take $R$ and reflect it along the $y$ direction to produce $R’=R(x,-y)$. The result of the point addtion is $P+Q=R’$.

What if we want to add two of the same point together: $P+P$ ? . We can’t draw a unique line through one point, but we can pick a unique line by calculating the tangent line to the curve at the point. Calculate the tangent line at the point $P$. Continue the line until it intersects with the curve at point $R$. Reflect this point as before: $P+P=R’=R(x,-y)$.

What happens if there is no third intersections ? Sometimes you will pick two points $P,Q$ and the line will not touch the curve again. In this case we say that the line intersects with the point (O) which is a single point located at the end of every vertical line at infinity. As such, point addtion for an elliptic curve is defined in 2D space, with an addition point located at infinity.

Included below is a diagram as a visual aid to these different cases: diagram of ECC addtion

The point 0 acts as the identity operator of the group: $P+0=P$ and $P+(-P)=0$

This brings us to the point of defining an elliptic curve.

Definition: An elliptic curve E is the set of solutions to a Weierstrass equation:$E:Y^2=X^3+aX+b$ together with a point at infinity $0$. The constant $a,b$ must be satisfy the relationship: $4a^3+27b^2 \ne 0$

to ensure there are no singularities on the curve.

Formally, let $E$ be an eliiptic curve, point addtion has the following properties:

(a) P+0 = 0+P=P

(b) P + (-P) = 0

(c) (P+Q) + R = P + (Q+R)

(d) P + Q = Q + P

In ECC, we study elliptic curves over a finite field $F_p$. This means we look at the curve modulo the characteristic p and an elliptic curve will no longer be a curve, but a collection of points whose x,y coordinates are integers in $F_p$

The following starter challenges will take you through the calculations for ECC and get you used to the basic operation that ECC is built upon, have fun !

Property $(d)$ shows that point addtion is communicative. The flag is the name we give groups with a commutative operation.

flag: Crypto{Abelian}

POINT NEGATION

In the background section, we covered the basics of how we can view point addtion over an elliptic curve as being an abelian group operation. In this geometric picture we allowed the coordinations on the curve to be any real number.

To apply elliptic curves in a cryptographic setting, we study elliptic curves which have coordinates in a finite field $F_p$

We will still be considering elliptic curves of the form: $E:Y^2=X^3+aX+b$, which satisfy the following conditions: $a,b\in F_p$ and $4a^3+27b^2\ne 0$. However, we no longer think of the elliptic curve as a geometric object, but rather a set of points defined by:

$E(F_p)=${$(x,y)\in F_p$ satisfying: $y^2=x^3+ax+b$}$\cup O$

Note: Everything we covered in the background still holds. The identity of the group is the point at infinity: O, and the addition law is unchanged. Given two point $E(F_p)$, the addition law will generate another point in $E(F_p)$

For all the challenges in the start set, we will be working with the elliptic curve

$E:Y^2=X^3+497X+1768,p:9739$

Using the above curve, and the point $P(8045,6936)$, find the point $Q(x,y)$ such that $P+Q=0$

Note: Remember, we’re working in a finite now, so you’ll need to work correctly with negative numbers.

This is solution:

We have $P+Q = 0 \implies Q=-P=(8045,-6936)$ (mod p)

$\implies Q(8045,-6936+9739)$

Imgur

flag: crpyto{8045,2803}

POINT ADDITION

While working with elliptic curve cryptography, we will need to add points together. In the background challenges, we did this geometrically by finding a line that passed through two points, finding the third intersection and then reflecting along the y-axis

Imgur

It turns out that there is an efficient algorithm for calculating the point addtion law for an elliptic curve.

Taken from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, the following algorithm will calculate the addition of two points on an elliptic curve

Algorithm for the addition of two points: P+Q

(a) If P=O, then P+Q=Q

(b) Otherwise, if Q=O, then P+Q=P

(d) If $x_1=x_2$ and $y_1=-y_2$ then $P+Q=O$

(e) Otherwise:

(e1) if $P\ne Q:\lambda = (y_2-y_1)/(x_2-x_1)$
(e2) if $P=Q:\lambda = (3x_1^2+a)/2y_1$

(f) $x_3 = \lambda^2-x_1-x_2,y_3 = \lambda(x_1-x_3)-y_1$

(g) $P+Q=(x_3,y_3)$

Note: We are working with a finite field, so the above calculation should be donw mod p, and we do not “divide” by an integer, we instead multiply by the modular inverse of a number. e.g. 1/5 = 9 mod 11

We will work with the following elliptic curve, and prime:

$E:Y^2 = X^3+497x+1769,P:9739$

Note: You can test your algorithm by asserting: X + Y = (1024, 4440) and X + X = (7284, 2107) for X = (5274, 2841) and Y = (8669, 740)

Using the above curve, and the points P = (493, 5564), Q = (1539, 4742), R = (4403,5202), find the point S(x,y) = P + P + Q + R by implemented the above algorithm

Note: After calculating S, substitute the coordinates into the curve. Assert that the point S is in $E(F_p)$

This is my solution

from Crypto.Util.number import *
inf = 1000000000000000000
p = 9739 
O = (inf%p,inf%p)
def sqr_mod(x):
    return x*x%p
def addition_point(P,Q):
    a = 497
    if(P==O):
        return Q 
    if(Q==O):
        return P 
    x_1 = P[0]
    y_1 = P[1]
    x_2 = Q[0]
    y_2 = Q[1]
    if(x_1==x_2 and y_1+y_2%p==0):
        return O 
    if(P!=Q):
        lamda1 = (y_2 - y_1 + p)%p 
        lamda2 = (x_2 - x_1 + p)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-y_1+p)%p 
        return (x_3,y_3) 
    if(P==Q):
        lamda1 = (3*sqr_mod(x_1)+a)%p 
        lamda2 = (2*y_1)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-P[1]+p)%p 
        return (x_3,y_3)
X = (5274, 2841) 
Y = (8669, 740)

# tmp = addition_point(X,X,497)
# print(tmp)
P = (493, 5564)
Q = (1539, 4742)
R = (4403,5202)
S = addition_point(P,addition_point(P,addition_point(Q,R)))
print(S)

flag: crypto{4215, 2162}

Scalar Multiplication

Scalar multiplication of two points is defined by repeated addtion: $3P=P+P+P$

In the next few challenges, we will use scalar multiplication to create a shared secret over an insecure channel similarly to Diffie-Hellman challenges.

Taken from ` “An Introduction to Mathematical Cryptography”, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman` , the following algorithm will efficiently calculate scalar multiplication of a point on an elliptic curve

Double and Add algorithm for the scalar multilication of point by n.

Input: P in $E(F_p)$ and an integer $n>0$

Set $Q=P$ and $R=O$
Loop while $n>0$
if n = 1 mod 2, R=R+Q
Set Q = 2 Q and n = [n/2] 5 if n>0, continue with loop at Step 2
Return the point R, which equal nP

Note: This is not the most efficient algorithm, there are many interesting ways to improve this calculation up, but this will be sufficient for our work

We will work with the following elliptic curve, and prime:

$Y^2 = X^3+497X+1768,p=9739$

Note: You can test your algorithm by asserting: $1337X = (1089,6931)$ for $X=(5323,5438)$

Using above curve, and the points P = (2339, 2213), find the point Q(x,y) = 7863 P by implementing the above algorithm

Note: After calculating Q, substitute the coordinates into the curve. Assert that the point $Q$ is in $E(F_p)$

This is my sol

from Crypto.Util.number import *
inf = 1000000000000000000
p = 9739 
O = (inf%p,inf%p)
def sqr_mod(x):
    return x*x%p
def addition_point(P,Q):
    a = 497
    if(P==O):
        return Q 
    if(Q==O):
        return P 
    x_1 = P[0]
    y_1 = P[1]
    x_2 = Q[0]
    y_2 = Q[1]
    if(x_1==x_2 and y_1+y_2%p==0):
        return O 
    if(P!=Q):
        lamda1 = (y_2 - y_1 + p)%p 
        lamda2 = (x_2 - x_1 + p)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-y_1+p)%p 
        return (x_3,y_3) 
    if(P==Q):
        lamda1 = (3*sqr_mod(x_1)+a)%p 
        lamda2 = (2*y_1)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-P[1]+p)%p 
        return (x_3,y_3)
X = (5274, 2841) 
Y = (8669, 740)

# tmp = addition_point(X,X,497)
# print(tmp)
P = (493, 5564)
Q = (1539, 4742)
R = (4403,5202)
S = addition_point(P,addition_point(P,addition_point(Q,R)))
print(S)

############# 

def scalar_multi(P,n):
    Q = P 
    R = O 
    while(n>0):
        if(n%2):
            R = addition_point(R,Q) 
        Q = addition_point(Q,Q)
        n=n//2 
    return R 
P = (2339, 2213)
n = 7863
nP = scalar_multi(P,n)
print(nP) 

flag: crypto{9467, 2742}

CURVES AND LOGS

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is the problem of finding an integer n such that Q=nP

Like we encounted with the discrete logarithm problem, scalar multiplication of a point in E(F_p) seems to be be a hard problem to undo, with the most efficient algorithm running at $p^{\frac{1}{2}}$ time.

This makes it a great candidate for a trapdoor function.

Alice and Bob are talking and they want to create a shared secret so they can start encrypting their messages with some symmetric cryptographic protocol.

Alice and Bob don’t trust their connection, so they need a way create a secret others ca’t replicate.

Alice and Bob agree on a curve E, a prime p and a generator point G

Note: In elliptic curve cryptographic, it is important that the order of G is prime. Constructing secure curves is complicated and it is recommended to use a preconstructed curve where a client is given the curve, the prime and the generator to use.

Alice generates a secret random integer $n_A$ and calculates $Q_A=n_AG$

Bob generates a secret random integer $n_B$ and calculates $Q_B=n_BG$

Alice sends Bob $Q_A$, and Bob sends Alice $Q_B$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate $n_{A\text{ / } B}$ in reasonable time.

Alice then calculates $n_AQ_B$, and Bob calculates $n_BQ_A$.

Due to the associativity of scalar multiplication, $S = n_AQ_B=n_BQ_A$

Alice and Bob can use S as their shared secret.

Using the curve, prime and generator:

$E: Y^2 = X^3+497X+1769 , p: 9739, G: (1804,5369)$

Calculate the shared secret after Alice sends you $Q_A = (815,3190)$, with your secret integer: $n_B = 1829$

Generate a key by calculating the SHA1 hash of the x coordinate (take the decimal representation of the coordinate and cast it to a string). The flag is the hexdigest you find.

This is my sol

from Crypto.Util.number import *
inf = 1000000000000000000
p = 9739 
O = (inf%p,inf%p)
def sqr_mod(x):
    return x*x%p
def addition_point(P,Q):
    a = 497
    if(P==O):
        return Q 
    if(Q==O):
        return P 
    x_1 = P[0]
    y_1 = P[1]
    x_2 = Q[0]
    y_2 = Q[1]
    if(x_1==x_2 and y_1+y_2%p==0):
        return O 
    if(P!=Q):
        lamda1 = (y_2 - y_1 + p)%p 
        lamda2 = (x_2 - x_1 + p)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-y_1+p)%p 
        return (x_3,y_3) 
    if(P==Q):
        lamda1 = (3*sqr_mod(x_1)+a)%p 
        lamda2 = (2*y_1)%p 
        lamda2 = inverse(lamda2,p)
        lamda = lamda1*lamda2%p 
        x_3 = (sqr_mod(lamda)-x_1-x_2+2*p)%p
        y_3 = (lamda*((x_1-x_3+p)%p)%p-P[1]+p)%p 
        return (x_3,y_3)
X = (5274, 2841) 
Y = (8669, 740)

# tmp = addition_point(X,X,497)
# print(tmp)
P = (493, 5564)
Q = (1539, 4742)
R = (4403,5202)
S = addition_point(P,addition_point(P,addition_point(Q,R)))
# print(S)

############# 

def scalar_multi(P,n):
    Q = P 
    R = O 
    while(n>0):
        if(n%2):
            R = addition_point(R,Q) 
        Q = addition_point(Q,Q)
        n=n//2 
    return R 

nB = 1829
Q_A = (815,3190)

S = scalar_multi(Q_A,nB)
print(S)

S = (7929,707)
flag: crypto{SHA1(7929)}
=> flag: crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}

EFFICIENT EXCHANGE

Alice and Bob are looking at the Elliptic Curve discrete Logarithm Problem and thinking about the data they send

They want to try and keep their data transfer as efficient as possible and realise that sending both the x and y coordinate of their public key isn’t nessary.

As long as Alice and Bob agree on the curve parameters, there are only ever two possible values of y for a given x

In fact, given either of the values of y permissible from the value x they receive, the x coordinate of their shared secret will be same

Note: For these challenges, we have used a prime p = 3 mod 4, which help you find y from $y^2$