The CRT-RSA cryptosystem is the most widely adopted RSA variant in digital applications. It exploits the properties of the Chinese remainder theorem (CRT) to elegantly reduce the size of the private keys. This significantly increases the efficiency of the RSA decryption algorithm. Nevertheless, an attack on RSA may also be applied to this RSA variant. One of the attacks is called partially known private key attack, that relies on the assumption that the adversary has knowledge of partial bits regarding RSA private keys. In this paper, we mount this type of attack on CRT-RSA. By using partial most significant bits (MSBs) of one of the RSA primes, p or q and its corresponding private exponent, d, we obtain an RSA intermediate. The intermediate is derived from $p-1$ and RSA public key, e. The analytical and novel reason on the success of our attack is that once the adversary has obtained the parameters: approximation of private exponent ${\tilde{d}}_p$, approximation of p, $\tilde{p}$ and the public exponent e where ${\tilde{d}}_p,\tilde{p},e=N^{\alpha /2}$ where $0<\alpha \le 1/4$ such that $|d_p-{\tilde{d}}_p|,|p-\tilde{p}|<N^{\frac{1-\alpha }{2}}$ and has determined the largest prime of $⌊\frac{p-1}{e}⌋$, it will enable the adversary to factor the RSA modulus $N=pq$. Although the parameter space to find the prime factor is large, we show that one can adjust its “success appetite” by applying prime-counting function properties. By comparing our method with contemporary partial key attacks on CRT-RSA, upon determining a suitable predetermined “success appetite” value, we found out that our method required fewer bits of the private keys in order to factor N.

This paper describes an attack on the Rivest, Shamir and Adleman (RSA) cryptosystem utilizing the modulus $N=p^{2}q$ where p and q are two large balanced primes. Let $e_1,e_2<N^{\gamma }$ be the integers such that $d_1,d_2<N^{\delta }$ be their multiplicative inverses. Based on the two key equations $e_1{d}_1-k_1\varphi \left(N\right)=1$ and $e_2{d}_2-k_2\varphi \left(N\right)=1$ where $\varphi \left(N\right)=p(p-1)(q-1)$, our attack works when the primes share a known amount of least significant bits (LSBs) and the private exponents share an amount of most significant bits (MSBs). We apply the extended strategy of Jochemsz–May to find the small roots of an integer polynomial and show that N can be factored if $\delta <\frac{11}{10}+\frac{9}{4}\alpha -\frac{1}{2}\beta -\frac{1}{2}\gamma -\frac{1}{30}\sqrt{180\gamma +990\alpha -180\beta +64}.$ Our attack improves the bounds of some previously proposed attacks that makes the RSA variant vulnerable.

Asymmetric key cryptosystem is a vital element in securing our communication in cyberspace. It encrypts our transmitting data and authenticates the originality and integrity of the data. The Rivest–Shamir–Adleman (RSA) cryptosystem is highly regarded as one of the most deployed public-key cryptosystem today. Previous attacks on the cryptosystem focus on the effort to weaken the hardness of integer factorization problem, embedded in the RSA modulus, $N=pq$ . The adversary used several assumptions to enable the attacks. For examples, p and q which satisfy Pollard’s weak primes structures and partial knowledge of least significant bits (LSBs) of p and q can cause N to be factored in polynomial time, thus breaking the security of RSA. In this paper, we heavily utilized both assumptions. First, we assume that p and q satisfy specific structures where $p=a^m+r_p$ and $q=b^m+r_q$ for $a,b$ are positive integers and m is a positive even number. Second, we assume that the bits of $r_p$ and $r_q$ are the known LSBs of p and q respectively. In our analysis, we have successfully factored N in polynomial time using both assumptions. We also counted the number of primes that are affected by our attack. Based on the result, it may poses a great danger to the users of RSA if no countermeasure being developed to resist our attack.

Boneh et al. introduced mediated RSA (mRSA) in 2001 in an attempt to achieve faster key revocation for medium-sized organizations via the involvement of a security mediator (SEM) as a semi-trusted third party to provide partial ciphertext decryption for the receiver. In this paper, a pairing-free security mediated encryption scheme based on an ElGamal variant is proposed. The scheme features a similar setting as in the mediated RSA but with a different underlying primitive. We show that the proposed security mediated encryption scheme is secure indistinguishably against chosen-ciphertext attack (IND-CCA) in the random oracle via the hardness assumption of the computational Diffie-Hellman (CDH) problem.

Rogue certificate authorities (RCA) are third-party entities that intentionally produce key pairs that satisfy publicly known security requirements but contain weaknesses only known to the RCA. This work analyses the Murru–Saettone RSA variant scheme that obtains its key pair from a potential RCA methodology. The Murru–Saettone scheme is based on the cubic Pell equation $x^3+r{y}^3+r^2{z}^3-3rxyz=1$. The public, e, and private, d key generation process uses the secret parameter $\psi =(p^2+p+1)(q^2+q+1)$ in place of the standard Euler–phi function $\varphi \left(N\right)=(p-1)(q-1)$, where $ed\equiv 1(mod\psi )$. We prove that, upon obtaining an approximation of $\psi$, we are able to identify the provided key pair that was maliciously provided even if the private key d size is approximate to $\psi$. In fact, we are able to factor the modulus $N=pq$.