首先选择两个相异大质数p、q,计算n=pq,取小于n的数e与(p-l)(q-l)互质。根据给定的e,再选择d满足ed除以z的模余数是1(即满足ed mod (p-l)(q-l)=1),根据欧几里得算法(a=bn+c,则a与b的最大公因子就等于b与c的最大公因子),这样的d-定可以找到。这样数对(n,e)为公钥,数对(n,d)为私钥在编码时,假设资料为A,将其分戍等长数据N块,每块为nKn。计算C=llle mod n,则c就是编码后的资料。至于解码,取III=Cd mod n。黑客攻击时怨得到e,这样就必须对n进行因式分解,选择足够大的质数p、q便能阻止分解因式。
对于p、q的选择,一般来说是足够大的素数,对于大数,并没有一个确定的界限,因为随着计算机技术的发展,破解能力正在逐步增强(根据摩尔定理计算能力18个月就翻一番)。RSA实验室的建议是,安全性要求相对较低时,p和q的乘积达到768位;安全性要求相对较高时,乘积达到1024位以上。