Cryptanalysis of the Chor—Rivest Cryptosystem

Knapsack-based cryptosystems used to be popular in the beginning of public key cryptography before all but the Chor—Rivest cryptosystem being broken. In this paper we show how to break this one with its suggested parameters: GF(p ²⁴ ) and GF(256 ²⁵ ) . We also give direction on possible extensions of our attack. Received 9 October 1998 and revised 25 July 1999     

基于AES和RSA的加密信息传送方案

AES私钥密码体制加解密效率高，但在密钥管理方面比较困难，而RSA公钥密码体制不存在密钥管理的问题，但是加解密效率很低。根据这两种密码体制的优缺点，提出了基于AES和RSA的加密信息传送方案。此方案不但改善了RSA加解密的速度慢的缺点，也解决了AES体制申密钥管理因难的问题。     

OAEP Reconsidered

The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard ``black box' security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure. The paper also presents a new scheme OAEP+ , along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP. It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out—essentially by accident, rather than by design—that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme.     

基于RSA的广播加密方案

提出一种基于RSA算法实现的广播加密方案,方案采用的是树形结构,密钥生成和分配过程简介,并且传输开销和存储开销与用户数量以及授权用户数量都没有关系,为常量级。与其它使用计算量较大的双线性映射构造的性能相同的方案相比较,本方案计算量较小。同时非授权用户不能通过共谋构造出一个不同的解密钥,即方案具有抗共谋性。方案能够实现对恶意共享解密钥的叛逆者的追踪。     

On Polynomial Approximation of the Discrete Logarithm and the Diffie—Hellman Mapping

We obtain several lower bounds, exponential in terms of lg p , on the degrees of polynomials and algebraic functions coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points; the number of points can be as little as p ^1/2 + ɛ . We also obtain improved lower bounds on the degree and sensitivity of Boolean functions on bits of x deciding whether x is a quadratic residue. Similar bounds are also proved for the Diffie—Hellman mapping g ^x → g ^x2 , where g is a primitive root of a finite field of q elements F _q . These results can be used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm and breaking the Diffie—Hellman cryptosystem. The method is based on bounds of character sums and numbers of solutions of some polynomial equations. Received 26 August 1997 and revised 29 June 1998     

Batch RSA

We present a variant of the RSA algorithm called Batch RSA with two important properties:

Fast public-key cryptosystem using congruent polynomial equations

A fast public-key cryptosystem is proposed which is based on congruent polynomial equations. This scheme is much faster than the RSA scheme. Moreover, the encryption and decyption algorithms for this scheme are very simple. The task of breaking this scheme appears to be as difficult as that of factoring a large composite integer, although this has not yet been proven.     

一种基于RSA的数字图象加密技术及其快速实现

RSA公钥密码体制的安全性依赖于大整数因数分解的困难性,目前安全素数产生难度大,运算时间长。文章根据素数的特殊表示法研究了一种高速的安全素数算法,针对当今的信息安全问题和数字图像的特点,提出了一种基于图像信息摘要和RSA的图像加密技术,利用图像信息摘要构造图像像素置乱矩阵并对图像像素矩阵进行置乱后再运用RSA公钥加密算法对置乱后的图像快速加密。     

可公开验证的ElGamal／RSA加密

可公开验证加密允许任何实体验证加密的消息和先前承诺的秘密一样,但不会泄漏明文的任何信息。这在公平交换、防欺骗的秘密分享和安全多方计算中有重要应用。该文分别给出可公开验证的ElGamal加密和RSA加密方案。其中前者是Stalderr方案的改进,改进后的方案是语义安全的而Stalder方案达不到语义安全性。同时将该方案推广到了多个接受者的情形,最后给出了高效的可公开验证RSA加密方案。     

Bulk encryption algorithm for use with RSA

The public-key cryptosystem known as RSA is widely judged to be secure, but in software implementations is slow, and even in hardware implementations encryption with a general 512-bit exponent runs only at tens of kilobits per second. Use of a small public exponent can speed encryption by up to 375-fold, but decryption speed can be increased only by four-fold in software or two-fold in hardware using the method of Quisquater and Couvreur (1982). It is therefore common to employ a second, fast, secret-key, cryptosystem such as the DES as the bulk encryption method, while the session key for that system is transferred using RSA. This however increases the security risk, as breaking either RSA or DES is sufficient to obtain knowledge of the plaintext, and DES in particular has been the subject of intense cryptanalytic activity in recent years. It is therefore desirable to use a fast secret-key bulk encryption algorithm whose security can be demonstrably related to that of RSA. The following proposed system, designated QS, goes some way to meeting this aim.<>     

Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups

We describe a short signature scheme that is strongly existentially unforgeable under an adaptive chosen message attack in the standard security model. Our construction works in groups equipped with an efficient bilinear map, or, more generally, an algorithm for the Decision Diffie-Hellman problem. The security of our scheme depends on a new intractability assumption we call Strong Diffie-Hellman (SDH), by analogy to the Strong RSA assumption with which it shares many properties. Signature generation in our system is fast and the resulting signatures are as short as DSA signatures for comparable security. We give a tight reduction proving that our scheme is secure in any group in which the SDH assumption holds, without relying on the random oracle model. An extended abstract entitled “Short Signatures Without Random Oracles” (Boneh and Boyen in Advances in Cryptology—EUROCRYPT 2004, LNCS, vol. 3027, pp. 56–73, 2004) appears in Eurocrypt 2004. Dan Boneh: Supported by NSF and the Packard Foundation.     

一种网络传输信息加密解密系统研制的方法

在对公钥密码体制分析的基础上，研究了RSA密码体制的实现算法，设计了系统程序模块。开发了端对端的网络传输信息加密解密系统。测试表明采用RSA密码体制可以研制出安全性更高的网络传输信息加密解密系统。     

RSA-Based Undeniable Signatures

We present the first undeniable signatures scheme based on RSA. Since their introduction in 1989 a significant amount of work has been devoted to the investigation of undeniable signatures. So far, this work has been based on discrete log systems. In contrast, our scheme uses regular RSA signatures to generate undeniable signatures. In this new setting, both the signature and verification exponents of RSA are kept secret by the signer, while the public key consists of a composite modulus and a sample RSA signature on a single public message. Our scheme possesses several attractive properties. First, provable security, as forging the undeniable signatures is as hard as forging regular RSA signatures. Second, both the confirmation and denial protocols are zero-knowledge. In addition, these protocols are efficient (particularly, the confirmation protocol involves only two rounds of communication and a small number of exponentiations). Furthermore, the RSA-based structure of our scheme provides with simple and elegant solutions to add several of the more advanced properties of undeniable signatures found in the literature, including convertibility of the undeniable signatures (into publicly verifiable ones), the possibility to delegate the ability to confirm and deny signatures to a third party without giving up the power to sign, and the existence of distributed (threshold) versions of the signing and confirmation operations. Due to the above properties and the fact that our undeniable nsignatures are identical in form to standard RSA signatures, the scheme we present becomes a very attractive candidate for practical implementations. Received 25 July 1997 and revised 5 November 1998     

NTRU公开密钥体制快速实现算法

NTRU算法是一种基于环的公开密钥体制,与RSA和ECC等典型的加密算法相比,在安全性和速度方面具有明显的优势.分析了目前NTRU算法的研究状况,提出了具体、完整和快速实现NTRU公开密钥体制的方法,包括产生随机多项式、卷积计算和模p计算算法.给出的方法适用与NTRU-1998、NTRU-2001和NTRU-2005.可以提高NTRU算法的速度达50%以上.     

Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. (Advances in Cryptology—EUROCRYPT 2004, ed. by C. Cachin, J. Camenisch, pp. 506–522, 2004) is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous identity-based encryption (IBE) scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous hierarchical identity-based encryption, public-key encryption with temporary keyword search, and identity-based encryption with keyword search. An extended abstract of this paper appears in Advances in Cryptology—CRYPTO 2005, ed. by V. Shoup, Santa Barbara, California, August 14–18, 2005, Lecture Notes in Computer Science, vol. 3621 (Springer, Berlin, 2005), pp. 205–222. This is the full version.     

QMLFD Based RSA Cryptosystem for Enhancing Data Security in Public Cloud Storage System

Nowadays sharing secure data turns out to be a challenging task for the data owner due to its privacy and confidentiality. Several IT companies stores their important information in the cloud since computing has developed immense power in sharing the data. On the other hand, privacy is considered a serious issue in cloud computing as there are numerous privacy concerns namely integrity, authentication as well as confidentiality. Among all those concerns, this paper focuses on enhancing the data integrity in the public cloud environment using Qusai modified levy flight distribution for the RSA cryptosystem (QMLFD-RSA). An effective approach named QMLFD for the RSA cryptosystem is proposed for resolving the problem based on data integrity in public cloud environment. A secured key generation and data encryption are done by employing the RSA cryptosystem thus the data is secured from unauthorized users. The key selection is done by using quasi based modified Levy flight distribution algorithm. Thus the proposed approach provides an effective model to enhance the integrity of data in cloud computing thus checking the data integrity uploaded in the public cloud storage system. In addition to this, ten optimization benchmark functions are calculated to determine the performances and the functioning of the newly developed QMLFD algorithm. The simulation results and comparative performances are carried out and the analysis reveals that the proposed QMLFD for the RSA cryptosystem provides better results when compared with other approaches.

     

A New and Improved Paradigm for Hybrid Encryption Secure Against Chosen-Ciphertext Attack

We present a new encryption scheme which is secure against adaptive chosen-ciphertext attack (or CCA2-secure) in the standard model (i.e., without the use of random oracle). Our scheme is a hybrid one: it first uses a public-key step (the Key Encapsulation Module or KEM) to encrypt a random key, which is then used to encrypt the actual message using a symmetric encryption algorithm (the Data Encapsulation Module or DEM). Our scheme is a modification of the hybrid scheme presented by Shoup in (Euro-Crypt’97, Springer LNCS, vol. 1233, pp. 256–266, 1997) (based on the Cramer–Shoup scheme in CRYPTO’98, Springer LNCS, vol. 1462, pp. 13–25, 1998). Its major practical advantage is that it saves the computation of one exponentiation and produces shorter ciphertexts.     

On the Importance of Eliminating Errors in Cryptographic Computations

We present a model for attacking various cryptographic schemes by taking advantage of random hardware faults. The model consists of a black-box containing some cryptographic secret. The box interacts with the outside world by following a cryptographic protocol. The model supposes that from time to time the box is affected by a random hardware fault causing it to output incorrect values. For example, the hardware fault flips an internal register bit at some point during the computation. We show that for many digital signature and identification schemes these incorrect outputs completely expose the secrets stored in the box. We present the following results: (1) The secret signing key used in an implementation of RSA based on the Chinese Remainder Theorem (CRT) is completely exposed from a single erroneous RSA signature, (2) for non-CRT implementations of RSA the secret key is exposed given a large number (e.g. 1000) of erroneous signatures, (3) the secret key used in Fiat—Shamir identification is exposed after a small number (e.g. 10) of faulty executions of the protocol, and (4) the secret key used in Schnorr's identification protocol is exposed after a much larger number (e.g. 10,000) of faulty executions. Our estimates for the number of necessary faults are based on standard security parameters such as a 1024-bit modulus, and a 2 ^-40 identification error probability. Our results demonstrate the importance of preventing errors in cryptographic computations. We conclude the paper with various methods for preventing these attacks. Received July 1997 and revised August 2000 Online publication 27 November, 2000     

Authenticated Key Exchange Provably Secure Against the Man-in-the-Middle Attack

The standard Diffie—Hellman key exchange is suseptible to an attack known as the man-in-the-middle attack. Lack of authentication in the protocol makes this attack possible. Adding separate authentication to the protocol solves the problem but adds extra transmission and computation costs. Protocols which combine the authentication with the key exchange (an authenticated key exchange) are more efficient but until now none were provably secure against the man-in-the-middle attack. This paper describes an authenticated key exchange based on the difficulty of the q th-root problem, a problem believed to be equivalent to the discrete logarithm problem over groups of order q ² (where q is a large prime) and parallel to the square-root problem over the ring modulo N , where N is a strong two prime composite integer. We show that mounting a man-in-the-middle attack for our protocol is equivalent to breaking the Diffie—Hellman problem in the group. Received March 2000 and revised August 2001 Online publication 23 November 2001     

Paillier''s Trapdoor Function Hides up to O ( n ) Bits

At EuroCrypt '99 Paillier proposed a new encryption scheme based on higher residuosity classes. The new scheme was proven to be one-way under the assumption that computing N -residuosity classes in Z _N2 ^* is hard. Similarly the scheme can be proven to be semantically secure under a much stronger decisional assumption: given w ∈ Z _N2 ^* it is impossible to decide if w is an N -residue or not. In this paper we examine the bit security of Paillier's scheme. We prove that if computing residuosity classes is hard, then given a random w it is impossible to predict the least significant bit of its class significantly better than at random. This immediately yields a way to obtain semantic security without relying on the decisional assumption (at the cost of several invocations of Paillier's original function). In order to improve efficiency we then turn to the problem of simultaneous security of many bits. We prove that Paillier's scheme hides n-b (up to O(n) ) bits if one assumes that computing the class c of a random w remains hard even when we are told that c<2 ^b . We thoroughly examine the security of this stronger version of the intractability of the class problem. An important theoretical implication of our result is the construction of the first trapdoor function that hides super-logarithmically (up to O(n) ) many bits. We generalize our techniques to provide sufficient conditions for a trapdoor function to have this property.