Dan Boneh密码学笔记14

Part 1 Elliptic curve cryptography

Elliptic curves.

–Over the reals.

Elliptic curve addition.

–Geometric and algebraic.

–Over finite fields, GF(p).

Part 2 ECC based crypto version

The ECDLP Problem:

-Getting a group.

-Order.

Diffie-Hellman Key Exchange.

Elliptic Curve Diffie-Hellman Key Exchange

Elliptic Curve El-Gamal.

Part3 Bilinear Pairing

Motivating the use of bilinear pairings.

Bilinear pairing

Security problems

Part4 Identity based Encryption

Part 1 Elliptic curve cryptography

Elliptic curves.

–Over the reals.

•Elliptic curve addition.

–Geometric and algebraic.

–Over finite fields, GF(p).

We have seen some problems, DLP, CDHP, DDHP which are considered hard. Some of these problems are over Abelian fields or groups.

We have looked at fields GF(p) where the elements of the field are simply integers, and the operations are modular. But these are not the only domains we can use. Miller and Koblitz, independently, suggested the use of elliptic curves for constructing public-key cryptosystems.

我们已经看到了DLP，CDHP，DDHP等一些很难解决的问题。其中一些问题涉及阿贝尔群或域。我们查看了域GF（p），其中字段的元素只是整数，并且操作是模。但这不是我们可以使用的唯一域。Miller和Koblitz分别建议使用椭圆曲线来构建公钥密码系统。

We can take an Elliptic curve over a field, GF(p), or GF(p^m). We are effectively restricting solutions to an equation to elements of a particular field. The problems like DLP are not necessarily hard in those fields, so we need to be a little careful.

我们可以在GF（p）或GF（p^m）上绘制椭圆曲线。我们正在有效地将方程的解决方案限制为特定领域的元素。像DLP这样的问题在这些领域中不一定很困难，因此我们需要谨慎一些。

Relative key sizes: For similar security

相对密钥大小：用于类似的安全性

Elliptic curves over the reals

实数上的椭圆曲线

椭圆曲线函数形式如下，ab是参数，要满足delta。

Elliptic curve “addition”椭圆曲线“加法”

To get to an Abelian group we need a commutative binary operation.

This addition can be defined geometrically, making use of intersections and mirror images. The addition can, alternately, be represented algebraically. The point at infinity acts as the identity.

要进入阿贝尔群，我们需要一个可交换的二进制运算。可以使用交点和镜像在几何上定义此加法。可替代地，该加法可以代数表示。无穷大的点充当身份。

Let P1 and P2 be elements of E. We can calculate P1+P2 geometrically by drawing a line through P1 and P2 and recording the point on interception of the curve. The reflection across the x axis and onto the elliptic curve E is the solution P1+P2.

令P1和P2为E的元素。我们可以通过在P1和P2上画一条线并记录曲线截距上的点来几何计算P1 + P2。沿着x轴并到达椭圆曲线E的反射是解P1 + P2。

How does infinity act as the identity? “A vertical line” hits the opposite side and reflects back.

无限如何充当身份？ “垂直线”击中了另一侧并向后反射。

What about algebraically?

在x1 = x2的情况下，刚才的公式没办法直接套。

如果y1 = -y2，所以这些点是逆的，并且我们得到一条垂直线，该线与设置在无穷大处的点（即在恒等式处）相交。这个点是单位元。

如果y1 = y2，所以我们是“加倍点”或将点加到自身上。在这种情况下，我们将曲线上的切线作为该点的直线。s求法改变一下。

Elliptic curves over GF(p)

The reals are an infinite field. In cryptography, the finite fields are more frequently used. We can consider elliptic curves where the operations are all carried out with the elements being elements of some field, and operations being “modular”.

实数是一个无限域。在密码中，有限域被更频繁地使用。我们可以考虑椭圆曲线，其中所有操作都是在元素是某个字段的元素的情况下执行的，并且操作是“模”。

模11，群里的元素有13个，在椭圆曲线上，生成元个数差不多就是模数左右浮动。我们算出12个点来，还有一个是无穷远点。

这块可能会考计算题。 要明白这个椭圆曲线函数后面默认加了mod11。

当x=2时，计算等式左边得到了5， y一个个试，计算y的平方mod11得到5的情况。发现是4，和4对应的还有-4，-4mod11 得到7 所以x=2时，y=4,7。椭圆曲线上的点有（2,4）（2,7）。

x只需要从0算到11-1（p-1）即可。

特别注意，这里不是除号！是逆。

逆就是某个数乘某个数模p等于1。

这里2的逆是9。因为2乘9mod17=1。

椭圆曲线上的点构加上无穷远点成一个循环子群。

这个椭圆曲线的位数为19，因为其包含19个点。

代入公式就行。注意，两个点一样的时候S的计算公式不同。计算S是逆不是除法。

这19个点是凌乱分布的，是不错的。

Part 2 ECC based crypto version

The ECDLP Problem:

-Getting a group.

-Order.

Diffie-Hellman Key Exchange.

Elliptic Curve Diffie-Hellman Key Exchange

Elliptic Curve El-Gamal.

The ECDLP Problem椭圆曲线离散对数问题

The most common hard problem that underlies the use of public key elliptic curve cryptosystems is the Elliptic Curve Discrete Logarithm Problem.

Let E be the set of points of our elliptic curve defined over the field GF(p).

The collection of points and the operation of addition, as defined earlier, form a group which we could denote E(GF(p)).

In this group the common operation is “scalar multiplication”.

使用公钥椭圆曲线密码系统的最常见难题是椭圆曲线离散对数问题。

令E为在GF（p）域上定义的椭圆曲线的点集。

如前面所定义，点的集合和加法运算构成了一个组，我们可以将其表示为E（GF（p））。

在该群中，常见的运算是“标量乘法”。

Notice that we have a group not a field.

Scalar multiplication is not an additional binary operation, rather is an extension of the addition rule.

We write scalar multiplication, of a point P, by an integer k as kP, and define it as P+P+…+P with k copies of P in the sum.

请注意，我们有一个群而不是一个域。

标量乘法不是附加的二进制运算，而是加法规则的扩展。

我们将点P的标量乘以整数k编写为kP，并将其定义为P + P +…+ P，其中有K个P的和。

We can now define the Elliptic Curve Discrete Logarithm Problem:

Given two points in E, P1 and P2, find k: P1=kP2.

现在，我们可以定义椭圆曲线离散对数问题：

给定E中的两个点P1和P2，求k：P1 = kP2。

Order … group and element …

我们用#E表示曲线上的点数，即E（GF（p））群中的元素数。

每个元素（点）P都有一个阶，最小元素x：xP = O（恒等式或点）。

如果群阶是质数，则是循环群，除无穷大点之外的所有元素都是生成元，并且所有元素的阶都等于群阶。

我们想要一个这样的阿贝尔群。

我们并不总是直接得到一个！

Diffie-Hellman Key Exchange

The first public key system.

Security is based on the difficulty of computing discrete logarithm.

Actually security it is based on the computational Diffie-Hellman problem.

System Setup：

A finite field Zp, where p is prime. A primitive element g ∈ Zp. p and g are public.

第一个公钥系统。

安全性基于计算离散对数的难度。

实际上，它是基于CDH问题的安全性。

系统设置：

有限域Zp，其中p是素数。基本元素g∈Zp。p和g是公开的。

EC Diffie-Hellman key exchange

我们可以在椭圆曲线上使用阿贝尔群进行类似的交换。

这两个用户在已知阶数n的域E（GF（q））上的曲线上以及在生成元P上的基点上达成一致。

EC El-Gamal

Part3 Bilinear Pairing

Motivating the use of bilinear pairings.

Bilinear pairing

Security problems

Motivating the use of bilinear pairings.

for example

Bilinear pairings

Weil Pairing

Tate Pairing

双线性对，这个性质记住。在椭圆曲线群加法上，括号内是加法，括号外的幂指数是乘法。ab可以这样乱跳。

Security for pairing over EC

Security depends on the hardness of one of a number of computational or decisional problems.

We have already seen the Elliptic Curve Discrete Log Problem (ECDLP).

We will now briefly look at the Bilinear Diffie-Hellman problem (BDHP).

安全性取决于许多计算或决策问题之一的难度。

我们已经看到了椭圆曲线离散对数问题（ECDLP）。

现在，我们将简要介绍双线性Diffie-Hellman问题（BDHP）。

BDHP，给定以下这个四元组，在不知道abc的情况下计算出e是困难的。

And, in the standard relationship manner, the corresponding BDH assumption is that there is no efficient algorithm to solve the BDHP with non-negligible probability.

并且，以标准关系方式，相应的BDH假设是没有有效的算法以不可忽略的概率求解BDHP。

CDH and DDH

对于椭圆曲线，这些表示为加法。

CDH: 给定P in G，xP和yP，计算xyP

DDH: 给定P in G，xP，yP和Q = zP，请确定z = xy。

DDH in pairing

Part4 Identity based Encryption（IBE）

This is a special type of public key cryptography. The idea is to simplify the management, distribution etc. of public keys. In traditional public key cryptography the key itself is a (fairly) random string managed within a public key infrastructure. Certificates are used to move trust from the key to a trusted entity, often a certificate authority. The certificate ties an identity and public-key (and corresponding secret private key) to each other. But their management is complicated.

这是一种特殊类型的公钥加密。这个想法是简化公钥的管理，分配等。在传统的公钥密码中，密钥本身是在公钥基础结构中管理的（相当）随机字符串。证书用于将信任从密钥转移到受信实体，通常是证书颁发机构。证书将身份和公钥（以及相应的私钥）相互关联。 但是他们的管理很复杂。

In identity based cryptography the idea (Shamir 1984) is to have an identity taking the role of identity and public key.The certificate trust is replaced through the use of a trusted authority which generates a private key for a user.

在基于身份的密码学中，这个想法（Shamir 1984）是让一个身份扮演身份和公钥的角色。证书信任通过使用为用户生成私钥的可信授权来替换。

The role of the TA

The TA issues private keys, and there may be many private keys associated with the same public key, which is just the identity.

-The identity, and therefore the public key, exists before the private key.

-However, the issue of the private key can be restricted in a time dependent manner, or on the basis of access control.

-Bob can encrypt a message for Alice@uow.edu.au (an identity for Alice) which Alice can only decrypt if she receives the private decryption key from the TA, which will only happen if she produces appropriate evidence as to who she is.

TA发布私钥，并且可能有许多与同一公钥关联的私钥，而这仅仅是身份。

身份（因此是公钥）位于私钥之前。

但是，可以以时间相关的方式或基于访问控制来限制私钥的发布。

Bob可以为Alice@uow.edu.au（Alice的身份）加密一条消息，只有当她从TA收到私有解密密钥时，该消息才可以解密，只有当她提供有关其身份的适当证据时，才会发生该消息。

The private key of the TA, and thus it’s responsibilities and rights, can be distributed to distribute trust.

The private key of an individual is established as a function of the master-key and the public key for that individual (or identity), which was generated earlier.

private-key=F(master-key,public-key).

TA的私钥及其职责和权利可以分发以分发信任。

根据较早生成的该个人（或身份）的主密钥和公共密钥来建立个人的私钥。

私钥= F（主密钥，公钥）。

ID-Based Crypto in practice

Originally only identity based signatures were known. In 2001 the first efficient and “secure” identity based encryption scheme was proposed (Sakai, Ohgishi, Kasahara). This was followed shortly after by Boneh-Franklin’s security model for identity based encryption, and a provably secure scheme. This was roughly the same scheme as Sakai et al. IND-ID-CPA secure, but transformable to IND-ID-CCA secure. The identity based encryption schemes rely primarily on bilinear pairings.

最初只知道基于身份的签名。 在2001年，提出了第一个有效且基于“安全”身份的加密方案（Sakai，Ohgishi，Kasahara）。随后不久，Boneh-Franklin推出了用于基于身份的加密的安全模型和可证明的安全方案。这与Sakai等人的方案大致相同。IND-ID-CPA安全，但可以转换为IND-ID-CCA安全。基于身份的加密方案主要依赖于双线性配对。

以前我们是公私钥对一起生成，都是随机的字符串。基于身份的加密IBE就是用固定的有意义的字符串作为公钥。比如，邮箱地址就是我的公钥。双线性对使这种想法可行。

以前我们有CA来为我们提供身份认证，数字签名。在IBE中，这个CA一般叫做PKG。Alice把自己的邮箱作为公钥，发给PKG，获得私钥。所以这个PKG权力很大。

具体算法如下，S是PKG生成主密钥mk的算法。

K输出给Alice的私钥dID。对应的公钥是这个ID。

E是Bob使用Alice的公钥ID加密消息m。pp是公开参数。

D是Alice使用私钥dID解密密文。

再实际使用中，需要对邮箱地址加个时间之类的随机值。以防私钥泄漏，导致全盘皆崩。

Boneh-Franklin IBE

上面这页最后一步是关键。

dID=sH1(ID)

s和t可以这么跳。

Security of IBE