首页
论坛
课程
招聘
[原创]记一道Android算法逆向题
2021-7-14 19:31 8454

[原创]记一道Android算法逆向题

2021-7-14 19:31
8454

一、题目

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 = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
q = 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解密
图片描述


[注意] 欢迎加入看雪团队!base上海,招聘安全工程师、逆向工程师多个坑位等你投递!

收藏
点赞1
打赏
分享
最新回复 (4)
雪    币: 536
活跃值: 活跃值 (425)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
wooyunking 活跃值 2021-7-15 14:30
2
0
牛逼
雪    币: 19
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
GTZ 活跃值 2021-7-16 14:40
3
0
大佬,有样本不?想自己试下
雪    币: 18
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
万里星河 活跃值 2021-7-16 14:57
4
0
牛逼
雪    币: 209
活跃值: 活跃值 (163)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
SmallDolphin 活跃值 2021-7-16 21:38
5
0
学习了,大佬Orz
游客
登录 | 注册 方可回帖
返回