The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about log ^1/2 q, but can be decreased to log log q with a running time q ^{O(1/log log q)} subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA).     

On the Linear Complexity and Multidimensional Distribution of Congruential Generators over Elliptic Curves

We show that the elliptic curve analogue of the linear congruential generator produces sequences with high linear complexity and good multidimensional distribution.communicated by: A. MenezesAMS Classification: 11T23, 14H52, 65C10     

On the Uniform Distribution of Certain Sequences

We investigate the uniform distribution of the sequence n as n ranges over the natural numbers and is a fixed positive real number which is not an integer. We then apply this in conjunction with the Linnik-Vaughan method to study the uniform distribution of the sequence p as p ranges over the prime numbers.     

低汉明重量序列的分布

数n的汉明重量是指n的二进制字符串表达式中数字1的个数,用Ham(n)来表示.低汉明重量序列在密码系统和编码理论中有非常广泛的应用.本文建立了低汉明重量数的序列表达式,并且利用指数和的上界以及Erd?s-Turán不等式证明低汉明重量序列的均匀分布性质,从而确保密码算法的随机性和运算效率.     

Computing the Rational Torsion of an Elliptic Curve Using Tate Normal Form

It is a classical result (apparently due to Tate) that all elliptic curves with a torsion point of order n(4?n?10, or n=12) lie in a one-parameter family. However, this fact does not appear to have been used ever for computing the torsion of an elliptic curve. We present here an extremely down-to-earth algorithm using the existence of such a family.     

On the uniformity of distribution of the RSA pairs

Let be a product of two distinct primes and . We show that for almost all exponents with the RSA pairs are uniformly distributed modulo when runs through

the group of units modulo (that is, as in the classical RSA scheme);

the set of -products , , where are selected at random (that is, as in the recently introduced RSA scheme with precomputation).

These results are based on some new bounds of exponential sums.

     

Rank 0 Quadratic Twists of a Family of Elliptic Curves

In this paper, we consider a family of elliptic curves over with 2-torsion part ₂. We prove that, for every such elliptic curve, a positive proportion of quadratic twists have Mordell–Weil rank 0.     

Reducing the Elliptic Curve Cryptosystem of Meyer-Müller to the Cryptosystem of Rabin-Williams

At Eurocrypt '96, Meyer and Müller presented a new Rabin-type cryptosystem based on elliptic curves. In this paper, we will show that this cryptosystem may be reduced to the cryptosystem of Rabin-Williams.     

Distribution Modulo 1 of Some Oscillating Sequences. III

For some oscillating functions, such as , we consider the distribution properties modulo 1 (density, uniform distribution) of the sequence , . We obtain positive and negative results covering the case when the factor is replaced by an arbitrary function of at most polynomial growth belonging to any Hardy field. (The latter condition may be viewed as a regularity growth condition on .) Similar results are obtained for the subsequence , taken over the primes      

Average Root Numbers for a Nonconstant Family of Elliptic Curves

We give some examples of families of elliptic curves with nonconstant j-invariant where the parity of the (analytic) rank is not equidistributed among the fibres.     

高阶椭圆型偏微分方程奇异摄动问题一致收敛差分格式

本文,我们讨论了一类高阶椭圆型偏微分方程奇异摄动问题。给出了连续问题解的先验估计。另外,我们还提供了一种数值求解该类问题的指数型差分格式。最后,证明了差分问题的解在能量范数意义下关于小参数一致收敛到连续问题的解。     

Degrees of the Elliptic Teichmüller Lift

The purpose of this paper is to find upper bounds for the degrees, or equivalently, for the order of the poles at O, of the coordinate functions of the elliptic Teichmüller lift of an ordinary elliptic curve over a perfect field of characteristic p. We prove the following bounds:ord₀(x_n)?−(n+2)pⁿ+npⁿ⁻¹, ord₀(y_n)?−(n+3)pⁿ+npⁿ⁻¹. Also, we prove that the bound for x_n is not the exact order if, and only if, p divides (n+1), and the bound for y_n is not the exact order if, and only if, p divides (n+1)(n+2)/2. Finally, we give an algorithm to compute the reduction modulo p³ of the canonical lift for p≠2,3.     

On the Density of Elliptic Curves

We show that 17.9% of all elliptic curves over Q, ordered by their exponential height, are semistable, and that there is a positive density subset of elliptic curves for which the root numbers are uniformly distributed. Moreover, for any > 1/6 (resp. > 1/12) the set of Frey curves (resp. all elliptic curves) for which the generalized Szpiro Conjecture |(E)| N _E ¹² is false has density zero. This implies that the ABC Conjecture holds for almost all Frey triples. These results remain true if we use the logarithmic or the Faltings height. The proofs make use of the fibering argument in the square-free sieve of Gouvêa and Mazur. We also obtain conditional as well as unconditional lower bounds for the number of curves with Mordell–Weil rank 0 and 2, respectively.     

关于αn~k模1的分布

讨论了αｎ￣ｋ模１的分布，证明了对于有无穷多个自然数ｎ满足     

A Formula for the Number of Elliptic Curves with Exceptional Primes

We prove a conjecture of Duke on the number of elliptic curves over the rationals of bounded height which have exceptional primes.     

On the Distribution Behaviour of Sequences

This paper presents results concerning those sets of finite Borel measures μ on a locally compact Hausdorff space X with countable topological base which can be represented as the set of limit distributions of some sequence. They arc characterized by being nonanpty, closed, connected and containing only measures μ with μ(X) = 1 (if X is compact) or 0 ≤ μ(X) ≤ 1 (if X is not compact). Any set with this properties can be obtained as the set of limit distributions of a sequence even by rearranging an arbitrarily given sequence which is dense in the sense that the set of accumulation points is the whole space X. The typical case (in the sense of Baire categories) is that a sequence takes as limit distributions all possible measures of this kind. This gives new aspects for the recent theory of maldistribukd sequences.     

On the Problem of Finite Signature

We show that not each model can be replaced by a model of finite signature so that its automorphism group remains the same.     

均匀分布与正态分布的教学设计

通过针对一元和二元均匀分布、正态分布实施重点教学,就概率统计的概念和知识点,讨论它们之间的联系及对比,再把分散的内容进行归纳。教学过程注重讲解均匀、正态反映的随机性的区别及各自的应用背景,使学生对这些抽象的概念有一个较生动化的认识．     

Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults

Elliptic curve cryptosystems in the presence of faults were studied by Biehl et al., Advances in Cryptology CRYPTO 2000, Springer Verlag (2000) pp. 131–146. The first fault model they consider requires that the input point P in the computation of dP is chosen by the adversary. Their second and third fault models only require the knowledge of P. But these two latter models are less practical in the sense that they assume that only a few bits of error are inserted (typically exactly one bit is supposed to be disturbed) either into P just prior to the point multiplication or during the course of the computation in a chosen location.This paper relaxes these assumptions and shows how random (and thus unknown) errors in either coordinates of point P, in the elliptic curve parameters or in the field representation enable the (partial) recovery of multiplier d. Then, from multiple point multiplications, we explain how this can be turned into a total key recovery. Simple precautions to prevent the leakage of secrets are also discussed.communication by : P. WildThe work described in this paper has been supported [in part] by the Commission of the European Communities through the IST Programme under Contract IST-1999-12324, http://www.cryptonessie.org/. The information in this document is provided as is, and no guarantee or warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at his sole risk and liability. The views expressed are those of the authors and do not represent an official view/position of the NESSIE project (as a whole)