# KJC Korea Journal Central

Korean | English

pISSN : 1598-849X / eISSN : 2383-9945

http://journal.kci.go.kr/jksci
• BACK
• TOP
Home > Explore Content > All Issues > Article View

A 2kβ Algorithm for Euler function φ(n) Decryption of RSA

• Publisher : The Korean Society Of Computer And Information
• Research Area : Computer Science

1강릉원주대학교

• There is to be virtually impossible to solve the very large digits of prime number p and q fromcomposite number n=pq using integer factorization in typical public-key cryptosystems, RSA. When the public key e and the composite number n are known but the private key d remainsunknown in an asymmetric-key RSA, message decryption is carried out by first obtaining φ(n)=(p-1)(q-1)=n+1-(p+q) and then using a reverse function of d=e-¹(modn)). Integerfactorization from n to p,q is most widely used to produce φ(n), which has been regarded asmathematically hard. Among various integer factorization methods, the most popularly used is thecongruence of squares of a² ≡b²(modn), a=(p+q)/2, b=(q-p)/2 which is more commonly used then n/p=q trial division. Despite the availability of a number of congruence of scares methods,however, many of the RSA numbers remain unfactorable. This paper thus proposes an algorithmthat directly and immediately obtains φ(n). The proposed algorithm computes 2kβj≡2t(modn), 0≤ i ≤ γ-1,k=1,2,⋯or 2kβj=2βj for 2j≡βj(modn),2 γ-1＜n＜2γ, j=γ-1,γ,γ+1 to obtain thesolution. It has been found to be capable of finding an arbitrarily located φ(n) in a range of n-10 ⌊√2⌋＜ φ(n) ≤ n-2⌊√2⌋ much more efficiently than conventional algorithms.

164 Viewed

Close X

# Citation

Close X
타입을 선택하세요 :
@article{ART001898121},
author={Sang-Un, Lee},
title={A 2kβ Algorithm for Euler function φ(n) Decryption of RSA},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={7},
pages={71-76}