RSA大数质因子分解
参考：
https://zhuanlan.zhihu.com/p/35661698 （主要参考，感谢作者）
B站技术蛋的RSA算法科普视频
https://zhuanlan.zhihu.com/p/48249182
以下两篇关于不经意传输：
https://cloud.tencent.com/developer/article/1955134
Java代码
package com.hzydbs.rsa;
import java.math.BigInteger;
/**
* 求最大公约数
*
* @author 北门大官人
*
*/
public class GCD {
/**
* <p>
* 辗转相除法求最大公约数
*
* @param a
* @param b
* @return
*/
public BigInteger gcd(BigInteger a, BigInteger b) {
if (b.equals(BigInteger.ZERO)) {
return a;
} else {
return gcd(b, a.mod(b));
}
}
/**
* <p>
* 扩展欧几里得算法：
* <p>
* 求ax + by = 1中的x与y的整数解（a，b互质）
*
* @param a
* @param b
* @return
*/
public BigInteger[] extGcd(BigInteger a, BigInteger b) {
if (b.equals(BigInteger.ZERO)) {
BigInteger x1 = BigInteger.ONE;
BigInteger y1 = BigInteger.ZERO;
BigInteger x = x1;
BigInteger y = y1;
BigInteger r = a;
BigInteger[] result = { r, x, y };
return result;
} else {
BigInteger[] temp = extGcd(b, a.mod(b));
BigInteger r = temp[0];
BigInteger x1 = temp[1];
BigInteger y1 = temp[2];
BigInteger x = y1;
BigInteger y = x1.subtract(a.divide(b).multiply(y1));
BigInteger[] result = { r, x, y };
return result;
}
}
}
package com.hzydbs.rsa;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* 主要用于计算超大整数超大次幂然后对超大的整数取模。 我在网上查询到这个算法叫做"蒙哥马利算法"。
*
* @author 北门大官人
*/
public class Exponentiation {
/**
* 超大整数超大次幂然后对超大的整数取模 (base ^ exponent) mod n
*
* @param base
* @param exponent
* @param n
* @return
*/
public BigInteger expMode(BigInteger base, BigInteger exponent, BigInteger n) {
char[] binaryArray = new StringBuilder(exponent.toString(2)).reverse().toString().toCharArray();
int r = binaryArray.length;
List<BigInteger> baseArray = new ArrayList<BigInteger>();
BigInteger preBase = base;
baseArray.add(preBase);
for (int i = 0; i < r - 1; i++) {
BigInteger nextBase = preBase.multiply(preBase).mod(n);
baseArray.add(nextBase);
preBase = nextBase;
}
BigInteger a_w_b = this.multi(baseArray.toArray(new BigInteger[baseArray.size()]), binaryArray, n);
return a_w_b.mod(n);
}
private BigInteger multi(BigInteger[] array, char[] bin_array, BigInteger n) {
BigInteger result = BigInteger.ONE;
for (int index = 0; index < array.length; index++) {
BigInteger a = array[index];
if (bin_array[index] == '0') {
continue;
}
result = result.multiply(a);
result = result.mod(n);
}
return result;
}
}
package com.hzydbs.rsa;
import java.math.BigInteger;
import java.security.SecureRandom;
/**
* RSA加密、解密、测试正确性
*
* @author 北门大官人
*
*/
public class RSA {
/**
* <pre>
def gen_key(p, q):
n = p * q
fy = (p - 1) * (q - 1)
e = 3889
# generate d
a = e
b = fy
r, x, y = ext_gcd(a, b)
print x
d = x
# 公钥 私钥
return (n, e), (n, d)
* </pre>
*
* @param p
* @param q
* @return
*/
public BigInteger[][] genKey(BigInteger p, BigInteger q) {
BigInteger n = p.multiply(q);
BigInteger fy = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger e = new BigInteger("65537");
// generate d
BigInteger a = e;
BigInteger b = fy;
BigInteger[] rxy = new GCD().extGcd(a, b);
BigInteger r = rxy[0];
BigInteger x = rxy[1];
BigInteger y = rxy[2];
BigInteger d = x;
// 对于计算出来的负数d，需要d=d+fy
if (d.compareTo(BigInteger.valueOf(0)) < 0) {
d = d.add(fy);
}
// 公钥 私钥
return new BigInteger[][] { { n, e }, { n, d } };
}
/**
* 加密
*
* @param m 被加密的信息转化成为大整数m
* @param pubkey 公钥
* @return
*/
public BigInteger encrypt(BigInteger m, BigInteger[] pubkey) {
BigInteger n = pubkey[0];
BigInteger e = pubkey[1];
BigInteger c = new Exponentiation().expMode(m, e, n);
return c;
}
/**
* 解密
*
* @param c
* @param selfkey 私钥
* @return
*/
public BigInteger decrypt(BigInteger c, BigInteger[] selfkey) {
BigInteger n = selfkey[0];
BigInteger d = selfkey[1];
BigInteger m = new Exponentiation().expMode(c, d, n);
return m;
}
public static void main(String[] args) {
// 公钥私钥中用到的两个大质数p,q'''
/*
BigInteger p = new BigInteger(
"106697219132480173106064317148705638676529121742557567770857687729397446898790451577487723991083173010242416863238099716044775658681981821407922722052778958942891831033512463262741053961681512908218003840408526915629689432111480588966800949428079015682624591636010678691927285321708935076221951173426894836169");
BigInteger q = new BigInteger(
"144819424465842307806353672547344125290716753535239658417883828941232509622838692761917211806963011168822281666033695157426515864265527046213326145174398018859056439431422867957079149967592078894410082695714160599647180947207504108618794637872261572262805565517756922288320779308895819726074229154002310375209");
*/
SecureRandom rnd=new SecureRandom();
BigInteger p = BigInteger.probablePrime(2500, rnd);
BigInteger q = BigInteger.probablePrime(2500, rnd);
System.out.println("p=" + p);
System.out.println("q=" + q);
RSA rsa = new RSA();
// 生成公钥私钥'''
// pubkey, selfkey = gen_key(p, q)
BigInteger[][] keys = rsa.genKey(p, q);
BigInteger[] pubkey = keys[0];
BigInteger[] selfkey = keys[1];
// 需要被加密的信息转化成数字，长度小于秘钥n的长度，如果信息长度大于n的长度，那么分段进行加密，分段解密即可。'''
BigInteger m = new BigInteger(
"29552253920430244480935420141729228591524107699469182582408239360121179899450577101476579710345554967100561598716023732513996495299410141662749947786005937244656977738527833097623686415626468060988878281679146322528426363279034015388479917760840595285028058423329215856830057760069403267618402231064409756303753621261963998813245801555345709331865159424057596639080245793103551936729636763453083968195850372838520989535777891088951977529791342466901072485266582229616711047022114660121787354697672738075015287123936759958670135509278509350942132843134489493757755637523878155960314647723130468403810490573692371076668554081340711245013791760785972574183759777397663251563223522608282216156466237180692442271370955990451855629775212854995231450914759478136490035502825158538196415358501643051890005641780888343155829469962364157099845810220506084696098509487269528261738091603323397419416656531789855253870506832308483358363624293730162838161876883346182295801408785755959876699692983735536512143262257444692944221679236546240285743514676999000313320454652069198094628016190512249847885741233538694420190674827537926410498871218493798919040337011039226994754553313541467307192132768688698365695235674392298409676883545188918324372058782178620981923190334246098709749931778763297900223981313803899058107970787765589467633684966955996721171175415015860487524541409512786880456374877432683366318130671454224149144855682834737499745953873548378153316742130648196857516669493425502266531024732408366848110881647");
System.out.println("被加密信息：" + m);
// 信息加密'''
BigInteger c = rsa.encrypt(m, pubkey);
System.out.println("密文：" + c);
// 信息解密'''
BigInteger d = rsa.decrypt(c, selfkey);
System.out.println("被解密后信息：" + d);
System.out.println("再生成一对公私钥");
p = BigInteger.probablePrime(2500, rnd);
q = BigInteger.probablePrime(2500, rnd);
System.out.println("p=" + p);
System.out.println("q=" + q);
keys = rsa.genKey(p, q);
pubkey = keys[0];
selfkey = keys[1];
d = rsa.decrypt(c, selfkey);
System.out.println("用新私钥解密原来的加密信息，得到：" + d);
}
}
输出：
p=207705994119526370635869161069954229565107391387932304286553703306274121740633492598868287084647560498962361499214780454785819463801042336298083151123748850658773816003307962941619802856793616120731378783956567022870348363943931882870047928671419853619800298795745829246629031588074575380073256206465894642012481605099372604844186271754793348159995014012945750624659636311109630232644471853209174147632930519002807323175412569886246072456133782441253328997579963555894686075100710472028876913448641629646655981966186844212452879306620361697658069477420761828919042003642944412273603431027195785616212879545811630007744756747682775115144655026132025713591801215667933217220274218162164878761832318548509324500279831774279464196793862379119772913462229607
q=348310505184729662936448255921060459025650190470407992725460408515791175907253795321475916262374052909971540852173723956024631301790912099677965846629870816661742620079406260416636667658419001319297834827736625724299337971361193483143324291127607755987650957491698589642857779249204597314804395301094241235207960037676472023337138228608255312461514687640507920192601273607211421082580682890779460019383429967949863786488245574406881037760527063281356991797695196210502353472562534425229257582836920659020851711042805411637850256413082315206646222557868545204744469779763851403488721666952406009130139948931659582618376856570810347739380323989258222820776273746099806485192655367017231064754230320347764582752041580638419274714391432700000459430743153231
被加密信息：29552253920430244480935420141729228591524107699469182582408239360121179899450577101476579710345554967100561598716023732513996495299410141662749947786005937244656977738527833097623686415626468060988878281679146322528426363279034015388479917760840595285028058423329215856830057760069403267618402231064409756303753621261963998813245801555345709331865159424057596639080245793103551936729636763453083968195850372838520989535777891088951977529791342466901072485266582229616711047022114660121787354697672738075015287123936759958670135509278509350942132843134489493757755637523878155960314647723130468403810490573692371076668554081340711245013791760785972574183759777397663251563223522608282216156466237180692442271370955990451855629775212854995231450914759478136490035502825158538196415358501643051890005641780888343155829469962364157099845810220506084696098509487269528261738091603323397419416656531789855253870506832308483358363624293730162838161876883346182295801408785755959876699692983735536512143262257444692944221679236546240285743514676999000313320454652069198094628016190512249847885741233538694420190674827537926410498871218493798919040337011039226994754553313541467307192132768688698365695235674392298409676883545188918324372058782178620981923190334246098709749931778763297900223981313803899058107970787765589467633684966955996721171175415015860487524541409512786880456374877432683366318130671454224149144855682834737499745953873548378153316742130648196857516669493425502266531024732408366848110881647
密文：7241339024148544379659284979991371008614040507243620421150799770488524128645764738821846700642590467913096659844624897346552373634954027488409631127570771391139969568503650530736258485427456790281650639401901516721690660917184489660537964450096521349299628483467611082805603310135527593980844780084991587142543419073220468057408165268964268246906208877740765178199016084472562393810389367011218677961039289760409655551990731282483651773334903874927777324731832714382395307264594705329122238999523812411288067010532884707144620794694834100725043011131896681551479175772235621357690779733496971945583773137282639193902851817457565106140979379252307430335652879592496910588060545794869208346038202198532122128827479623672130267386311622763396036727358800902891232463840307275407451106639976927242026502998019379413869727566040720820323570408898574156747419782011184696927348855403350895966224792837275679413981580211448662455732275188558169935142012913563951542569430470362911248208429394092682179042370187856557661647676391968644067368663526251858079355225379683452125155280642869731326947638187446212303994162390663738604651513747888786731347178190949503034855566049329567245079937146795905005078336392567728787898355171185066540096530733535894598787334864407163333788766513927212184370297779225862069039330745732479084932093127740666558467306200606016527483322566882042593599315493959827699110776770483511132636336005409246897136115874770623757165635076002713618465968436479197609049706895215140734272059
被解密后信息：29552253920430244480935420141729228591524107699469182582408239360121179899450577101476579710345554967100561598716023732513996495299410141662749947786005937244656977738527833097623686415626468060988878281679146322528426363279034015388479917760840595285028058423329215856830057760069403267618402231064409756303753621261963998813245801555345709331865159424057596639080245793103551936729636763453083968195850372838520989535777891088951977529791342466901072485266582229616711047022114660121787354697672738075015287123936759958670135509278509350942132843134489493757755637523878155960314647723130468403810490573692371076668554081340711245013791760785972574183759777397663251563223522608282216156466237180692442271370955990451855629775212854995231450914759478136490035502825158538196415358501643051890005641780888343155829469962364157099845810220506084696098509487269528261738091603323397419416656531789855253870506832308483358363624293730162838161876883346182295801408785755959876699692983735536512143262257444692944221679236546240285743514676999000313320454652069198094628016190512249847885741233538694420190674827537926410498871218493798919040337011039226994754553313541467307192132768688698365695235674392298409676883545188918324372058782178620981923190334246098709749931778763297900223981313803899058107970787765589467633684966955996721171175415015860487524541409512786880456374877432683366318130671454224149144855682834737499745953873548378153316742130648196857516669493425502266531024732408366848110881647
再生成一对公私钥
p=273592101471818945571881524219361920560443779203827473459751290858352146592152279126682355504289457293693550766332747072095838560206621526758917260061112654933135465300082805884487473196367679211464600301051832755293964770080286404297719253466611284613942292764400476057596463027958592665841846040074179573410070018548532033034908199542401360516920719816841124620928412495002590155696641959444384118539023756818135896496906104614946111929456501917177873888775172283221129218548990243312701311635352661346339727659084429822155432014477474588082618480217728732086016111025091584381155086433657468469978378687329590772381981211789870919801284417534319413689904830835630041283456614452600624838325715796407488451179477894877244456133224738723620231709578951
q=188013569879983117122188708891765309755871325850276616379679080658502805953589292452815703093805334451252146223340042334389608705085724906971274546936095978363301312910048601843746498632428982282511837742009247942543808889090306130955044255960058599895401965526080755167610464140171299370089152319802987592819496228040588699909935657542034463611524311677533947690391052528280791362907512230099295782453080773545437052825088378929112374980564292575483728273390532664786657674601619454268798463241587446029369596747444761596745656556330853689082586759798297575233463700083113511424314537589766408593516585373267809159019845231662854333756468692017089372215150924998684765994155975086438185072359585201862031153379318663739588668247186995359151420449382003
用新私钥解密原来的加密信息，得到：18259918059527759548487951070183520295246233481885520781797768597066352263621649236861652337183261298219474594833820535902293870683655187091416805818732647276590736076879458108766582219480692118863022465693582453155979588178869696079067490915089918621300303241749019230724814474961306923977250359784016274463872302986772233965856207657672478859833497173152229586185433670992262390304530946418618453883829366399606252713092908878231225606824295889056012106669828875777281482586755439960160449074682581010440386361418220700695023325744755086266145954868791645225539436133077799789602002642965075084086030377835091930242650046725770643815008186562586951871422439989485155272573883962758077481846919939615055985374182469283166173716392330703915402868044306898930747075785897585904779112891750893963510532800153759477547559745387157414387438681216395382999856756212887982102413137186951322856277675609906034395944270822301718419317573848938076715731520609087232395321695442221314320911656620741415280669701354905397633822134261507938102495854416080142410067136035495658533559578478736237876168777207847224868852633942463748143195060794689756385143805279516460579460361454794817209780650057978630265718530285803179190209306958904308107835226307927808045356644129506928098043847721343865917246346202003468495494668226687474760031011497468632335698238090683938945924791754700183333549825516451519679013991177563689996157268440721042674532296376207340761749944055477340187730993442761059508781379826732088485234746
结论
基于RSA的不经意传输关键的一个问题解决了：客户端把AES密钥用n个公钥中的一个加密之后，服务端用所有的n个私钥去解密，都会得到大整数，且这n个大整数没有规律，服务端无法判断哪个是客户端真正的AES密钥明文。
服务端用得到的这n个AES密钥（只有一个是真正的、但服务端不知道）分别去对业务数据去做AES加密，然后把n个业务数据密文返回给客户端，客户端用真正的AES密钥去解密选择的业务数据，且只能解密该条业务数据。
