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.

Cryptographic key sharing methods for multi-groups are proposed with threshold access schemes, and the methods are analyzed for safety and reliability, the measures of security. The threshold access scheme is extended from the members in a single group to members in multi-groups of equal or hierarchical status. In the horizontal scheme, agreement between a certain number of groups makes the secret key accessible. In the vertical scheme, agreement of a high level group or agreement between two groups at high and low level makes the secret key accessible. To realize these access schemes, mutually relative polynomials are proposed and the distributed keys are generated and synthesized by interpolation. The equipment and configuration to manage these methods are also explained. The system miss-access and inaccessibility rates of each scheme are formulated, and the characteristics of these schemes are evaluated by numerical examination. It is confirmed that sharing methods for multi-groups have greater safety than for single group.

This paper proposes a dynamically randomized version of DES (called RDES) in which a input-dependent swapping Sk(X) is added onto the right half of the input in each round of DES. This new scheme decreases the probability of success in differential cryptanalysis because it decreases the characteristic probability. Each "best" two-round characteristic probability is analyzed for typical schemes of the RDES: (i) RDES-1 with a simple one-level swapping, (ii) RDES-1' with an optimal one-level swapping, (iii) RDES-2 with a simple two-level swapping, and (iv) RDES-2' with an optimal two-level swapping. The main results are as follows. (a) The differential attacks on the 16-round RDES-1' and the 16-round RDES-2 require more computational time than the exhaustive search. (b) A differential attack is substantially inapplicable to the 16-round RDES-2' because more than 263 chosen plaintext pairs are required. (c) The encryption/decryption speed of the n-round RDES is almost the same as that of the n-round DES.

We propose a new randomized version of DES in which a key-dependent swapping is used to strengthen DES and DES-like cryptosystems against differential cryptanalysis. This new scheme, called RDES, decreases the probability of success in differential attack by decreasing the characteristic probability. The characteristic is the effect of particular differences in plaintext pairs on the differences in the resultant ciphertext pairs. The characteristic probability for the n-round RDES is 2-n+1 times that for the n-round DES. As for the differential cryptanalysis based on characteristics, the 16-round RDES is as strong as the about 20-round DES. Encryption/decryption speed of n-round RDES is almost the same as that of the n-round DES.

In this paper, we propose two-dimensional public key cryptosystems. We show the cryptosystems based on three schemes: the Rabin, the Williams and the RSA. It is proved that complete breaking of the proposed two-dimensional cryptosystems based on the Rabin scheme or the Williams scheme is computationally equivalent to factoring n used as the modulus. It is also proved that solving for relational information such as the ratio of plaintext pair for these systems is computationally equivalent to factoring n. It is shown that both two-dimensional cryptosystems based on the Williams scheme and the RSA scheme are uniquely decipherable.

Super-anomalous elliptic curves over a ring Z/nZ ;(n=Πi=1k piei) are defined by extending anomalous elliptic curves over a prime filed Fp. They have n points over a ring Z/nZ and pi points over Fpi for all pi. We generalize Satoh-Araki-Smart algorithm and Ruck algorithm, which solve a discrete logarithm problem over anomalous elliptic curves. We prove that a "discrete logarithm problem over super-anomalous elliptic curves" can be solved in deterministic polynomial time without knowing prime factors of n.

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.

RDES cryptosystem is an n-round DES in which an probabilistic swapping is added onto the right half of the input in each round. It is more effective than a simple increase of DES rounds for a countermeasure against differential attack. In this paper, we show that the RDES is also effective against linear cryptanalysis. We applied Matsui's search algorithm to find the best expression for RDES-1 and RDES-2. The results are as follows: (a) The 16-round RDES-1 is approximately as strong as a 22-round DES, and the 16-round RDES-2 is approximately as strong as a 29-round DES. (b) Linear cryptanalysis for a 16-round RDES-1 and a 16-round RDES-2 requires more than 264 known-plaintexts.

We create a new version of the FEAL-N(X) cryptographic function, called FEAL-N(X)S, by introducing a dynamic swapping function. FEAL-N(X)S is stronger against Differential Cryptanalysis in the sense that any characteristic for FEAL-N(X) is less effective when applied to FEAL-N(X)S. Furthermore, the only iterative characteristics. that may attack the same number of rounds for the two versions are the symmetric ones, which have an average probability bounded above by 2-4 per round, i.e., the FEAL-N(X)S is at least as strong as DES with respect to this type of characteristic. We also show that in general the probability of an iterative characteristic for the FEAL-N(X) that is still valid for FEAL-N(X)S is decreased by 1/2 per round. Some of the best characteristics are shown. Experimental results show that the running time required by FEAL-N(X)S is around 10% greater compared to FEAL-N(X), in software; but this price is small compared to the gained strength against Differential Cryptanalysis.

To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {gx1, gx2, , gxs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.

A fast method for computing a multiple mP for a point P on elliptic curves is proposed. This new method is based on optimal addition sequences and the Frobenius map. The new method can be effectively applied to elliptic curves E(Fqn), where q is a prime power of medium size (e.g., q 128). When we compute mP over curves E(Fqn) with qn of nearly 160-bits and 11 q 128, the new method requires less elliptic curve additions than previously proposed methods. In this case, the average number of elliptic curve additions ranges from 40 to 50.

We propose an RSA-type scheme over the nonsingular part of a singular cubic curve En (0,b) : y2x3+bx2 (mod n), where n is a product of form-free primes p and q. Our new scheme encrypts/decrypts messages of 2 log n bits by operations of the x and y coordinates. The decryption is carried out over Fp or a subgroup of a quadratic extension of Fp, depending on quadratic residuosity of message-dependent parameter b. The decryption speed in our new scheme is about 4.6 and 5.8 times faster than that in the KMOV scheme and the Demytko scheme, respectively. We prove that if b is a quadratic residue in Zn, breaking our new scheme over En(0,b) is not easier than breaking the RSA scheme.

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.

This paper presents a zero-knowledge interactive protocol that demonstrates two factors a and b of a composite number n (=ab) are really known by the prover, without revealing the factors themselves. Here the factors a and b need not be primes. The security of the protocol is based on the difficulty of computing discrete logarithms modulo a large prime.

We have done a computer search for solutions of the equation x3y3z3n in the range max (|x|, |y|, |z|) 3414387 and 0 n 1000. We have discovered 21 new integer solutions for n {39, 143, 180, 231, 312, 321, 367, 439, 462, 516, 542, 556, 660, 663, 754, 777, 870}. As a result, there are 52 values of n (except n 4 (mod9)) for which no solutions are found.

Let N(k,pm) be the number of distinct values of xk mod pm for all integers x(0xpm-1). Given a random integer a, the probability that xka(mod pm) has an integer solution x is given by N(k,pm)/pm. Explicit and simple representations of N(k,pm) are obtained. Asymptotic formulas of the probability N(k,pm)/pm as m,p and k are also shown.

The basic operation in elliptic cryptosystems is the computation of a multiple dP of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.

Two methods of the second step of the elliptic curve method for factoring are known. One is the standard method that is similar to the second step of the p-1 method, and the other is the Brent method that is based on the "birthday paradox." In this paper, we propose a revised standard method and a revised Brent method. On an average, the revised standard method is the most efficient, the standard method is the second efficient, the revised Brent method is the third and the Brent method is the fourth. If the largest prime factor on the order of an elliptic curve is congruent to 1 modulo 3, then the revised Brent method becomes more efficient than the standard method. By applying these methods to unsolved problems in the Cunningham project, we found 18 new prime factors. The largest prime factor among them was 43-digits.