Cryptanalysis

Authors: Kenta Tani and Noboru Kunihiro Abstract: The secure implementation of the Greatest Common Divisor (GCD) algorithm is fundamental for many cryptographic schemes. The binary GCD algorithm has a highly input-dependent behavior. Therefore, we must carefully implement the binary GCD used in cryptographic systems. However, it has been noted that the binary GCD algorithm implemented in OpenSSL 1.1.0-1.1.0h and 1.0.2b-1.0.2o is not secure. Aldaya et al. presented this vulnerability at CHES2019. They also proposed a side-channel attack to collect sequences of operations performed by the binary GCD algorithm and an error correction algorithm (AGTB algorithm) to recover the LSBs of secret keys from the noisy sequences. In this paper, we propose an error correction algorithm that, like the AGTB algorithm, focuses on only a single type of error. We evaluate our algorithm using numerical experiments that reveal that our algorithm achieves a higher recovery rate than the AGTB algorithm. ...

Authors Mengce Zheng, Noboru Kunihiro, Yuanzhi Yao Abstract RSA (Rivest-Shamir-Adleman) cryptosystem is the most popular asymmetric key cryptographic algorithm used in computer science and information security. Recently, an RSA-like cryptosystem was proposed using a novel product that arises from a cubic field connected to the cubic Pell equation. The relevant key equation is $ed = 1 \bmod (p^2+p+1)(q^2+q+1)$ with $N=pq$. This RSA variant is claimed to be robust against the Wiener’s attack and hence the bit-size of the private key could be shorter, namely $d < N^{1/4}$. In this paper, we explore the further security analysis and investigate the potential small private exponent attack. We show that such RSA variant is particularly vulnerable to the lattice-based method. To be specific, we can carry out the lattice-based small private exponent attack if $d < N^{2-√2}}$, which is less secure than the standard RSA. Furthermore, we conduct numerical experiments to verify the validity of the proposed attack." ...