-
-
[原创]记一道Android算法逆向题
-
2021-7-14 19:31
-
一、题目
1、android 逆向题
小伙伴发来的题，说是强网杯的题
2、涉及算法
RSA
魔改Base64
二、解题过程
1、java层
2、native层
根据动态调试，如果调试不起来需要运行下断点，取一下运行的内存地址，alt+g改一下thumb 就可以调试了
发现大数
加密函数
输入 “1111”，
入参变为 0x31313131
加密结果为
根据以上信息判断可能是RSA加密，根据RSA加解密的数学原理
加密
c = (p ^ e) mod n;
解密
p = (c ^ d) mod n;
将大数0x1321d2fddde8bd9dff379aff030de205b846eb5cecc40fa8aa9c2a85ce3e992193e873b2bc667dabe2ac3ee9dd23b3a9ed9ec0c3c7445663f5455469b727dd6fbc03b1bf95d03a13c0368645767630c7eabf5e7ab5fa27b94ade7e1e23bcc65d2a7ded1c5b364b51
转为为
2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
质因数分解
1 2 | p = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711q = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367 |
使用py gmpy2 模块求d
1 | d=gmpy2.invert(e, (p-1)*(q-1)) |
ps：e在上图加密函数通过参数可以看到 e=0x10001
验证一下入参“0x31313131”与加密结果关系
1 2 3 4 | 0x621ef786a7c1eff5791988eb3120ee97654298b74e11cba7ed474bbdd8ce65d7755a4fb6fcb4ddc90a1241e05727e10ca753ed5da7d52282ced0d775001595889abe5714fb50d34e32519a9caf108cf8c29c7f39b73817c309904cad184e68c80ca57f983be328e加密686053924117469764358154772874732649247385652874103246772739306743770197632486049681714074769758785577275011175585848494941733554177924807348171671019631786626588395169172972504593136290022206683266871688618315385264595076872580347817678576231002766解密0x31313131 |
至此rsa加密结束
继续调试发现魔改base64
加密后结果
加密过程：
1 | flag->rsa->base64>与“bborOT+ohG*,U:;@/gVIAZ-,t++LaZkOrk?UcSOKJ?p-J+vuSN?:e,Kc/?h-oH?:tthoqYYSPp-ZC+Yw:*jrxPymGYO/PvDOIivNYtvJ?Mi*GG+/lmqEysrTdSD+eP+moP+l?+Np/oK=”进行比较 |
解密过程：
由于base64是魔改的，且table中有2个+和2个-，进行正常的逆推是求不出来结果的，所以要进行破魔，构造出
1 | bborOT+ohG*,U:;@/gVIAZ-,t++LaZkOrk?UcSOKJ?p-J+vuSN?:e,Kc/?h-oH?:tthoqYYSPp-ZC+Yw:*jrxPymGYO/PvDOIivNYtvJ?Mi*GG+/lmqEysrTdSD+eP+moP+l?+Np/oK= |
所有可能加密的字符，然后通过base64解密，rsa解密来求flag
"+"对应"["和"]"
"-"对应"("和")"
构造出2^14个加密字符串
使用
1 | abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ*[,(./:;?@]) |
进行base64解密
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
