This paper proposes a new RSA-type scheme over non-singular parts of singular cubic curves En(α,β):(y-αx)(y-βx)x3(mod n). In usual one-to-one communication, we prove that breaking the proposed scheme is not easier than breaking the RSA scheme for the whole ciphertexts. If encryption key e is larger than 19 for 512 bits modulus n, then the proposed scheme is secure against the Hastad attack in broadcast applications. A plaintext of two blocks, i.e., x and y coordinates in En(α,β), is encrypted to a ciphertext of three blocks, where the size of one block is log2n bits. The decryption speed ofthe proposed scheme is as fast as that of the RSA scheme for the even block plaintext.

A new algorithm for multiple-precision modular multiplication is proposed. It is fast and uses a small amount of main memory, and hence, is useful for application of a public-key cryptosystem to small computers, such as card computers.

This paper proposes RSA-type cryptosystems over elliptic curves En(O, b) and En(a, O),where En(a, b): y2 x3+ax+b (mod n),and n is a product of from-free primes p and q. Although RSA cryptosystem is not secure against a low exponent attack, RSA-type cryptosystems over elliptic curves seems secure against a low multiplier attack. There are the KMOV cryptosystem and the Demytko cryptosystem that were previously proposed as RSA-type cryptosystems over elliptic curves. The KMOV cryptosystem uses form-restricted primes as p q 2(mod 3)or p q 3(mod 4), and encrypts/decrypts a 2log n-bit message over varied elliptic curves by operating values of x and y coordinates. The Demytko cryptosystem, which is an extension of the KMOV cryptosystem, uses form-free primes, and encrypts/decrypts a log n-bit message over fixed elliptic curves by operating only a value of x coordinates. Our cryptosystems, which are other extensions fo the KMOV cryptosystem, encrypt/decrypt a 2log n-bit message over varied elliptic curves by operating values of x and y coordinates. The Demytko cryptosystem and our cryptosystems have higher security than the KMOV cryptosystem because from-free primes hide two-bit information about prime factors. The encryption/decryption speed in one of our cryptosystems is about 1.25 times faster than that in the Demytko cryptosystem.

From a practical point of view, a cryptosystem should require a small key size and less running time. For this purpose, we often select its definition field in such a way that the arithmetic can be implemented fast. But it often brings attacks which depend on the definition field. In this paper, we investigate the definition field Fp on which elliptic curve cryptosystems can be implemented fast, while maintaining the security. The expected running time on a general construction of many elliptic curves with a given number of rational points is also discussed.

Koblitz and Miller proposed a method by which the group of points on an elliptic curve over a finite field can be used for the public key cryptosystems instead of a finite field. To realize signature or identification schemes by a smart card, we need less data size stored in a smart card and less computation amount by it. In this paper, we show how to construct such elliptic curves while keeping security high.

In this paper an identity-based non-interactive key sharing scheme (IDNIKS) is proposed in order to realize the original concept of identity-based cryptosystem, of which secure realization scheme has not been proposed. First the necessary conditions for secure realization of IDNIKS are considered from two different poinrts of view: (i) the possibility to share a common-key non-interactively and (ii) the security for entity's conspiracy. Then a new non-interactive key sharing scheme is proposed, of which security depends on the difficulty of factoring. The most important contribution is to have succeeded in obtaining any entity's secret information as an exponent of the obtainer's identity information. The security of IDNIKS for entity's conspiracy is also considered in details.

For improving the RSA cryptosystem, more desirable conditions on key structures have been intensively studied. Recently, M.J.Wiener presented a cryptanalytic attack on the use of small RSA secret exponents. To be secure against the Wiener's attack, the size of a secret exponent d should be chosen more than one-quarter of the size of the modulus n = pq (in bits). Besides, it is more desirable, in frequent cases, to make the public exponent e as small as possible. However if small d is chosen first, in such case as the digital signature system with smart card, the size of e is inevitably increased to that of n when we use the conventional key generation algorithm. This paper presents a new algorithm, Algorithm I, for generating of the secure RSA keys against Wiener's attack. With Algorithm I, it is possible to choose the smaller sizes of the RSA exponents under certain conditions on key parameters. For example, with Algorithm I, we can construct the RSA keys with the public exponent e of two-thirds and secret exponent d of one-third of the size of modulus n (in bits). Furthermore we present a modified version of Algorithm I, Algorithm II, for generating of the strong RSA keys having the difficulty of factoring n. Finally we analyze the performances of Algorithm I and Algorithm II.

In 1990, Menezes, Okamoto and Vanstone proposed a method that reduces EDLP to DLP, which gave an impact on the security of cryptosystems based on EDLP. But this reducing is valid only when Weil pairing can be defined over the m-torsion group which includes the base point of EDLP. If an elliptic curve is ordinary, there exists EDLP to which we cannot apply the reducing. In this paper, we investigate the condition for which this reducing is invalid.

We propose two types of public-key cryptographic schemes based on elliptic curves modulo n, where n is the product of secret large primes p and q. The RSA-type scheme has an encryption function with an odd multiplier. The Rabin-type scheme has an encryption function with a multiplier of 2. The security of the proposed schemes is based on the difficulty of factoring n. Other security characteristics are also discussed. We show some applications to a master key scheme and blind signature scheme.