乘法逆元 + struct库学习！这两个知识点拖了好久，这几天终于把他们学习了一部分

0x00 乘法逆元

参考文章：https://zhuanlan.zhihu.com/p/378728642

事实证明有时候爆破和Z3不好使就得想想这个

言简意赅

3 * 6 mod 7 = 4
invert(6, 7) = 6 # 6 * 6 mod 7 = 1
4 * 6 mod 7 = 3

（公式块真好玩，到网页直崩呜呜呜）

0x01 struct

https://blog.csdn.net/qq_30638831/article/details/80421019

终于把这个模块学了，不用跑去DEV调数据的大端小端序了（python真好

文章参考

https://blog.csdn.net/weixin_52640415/article/details/125005006

HI

所以这次其实两道题都是乘模运算，第一题直接Z3秒了，第二题想着爆破都爆不出来就懵了

然后知道了乘模运算怎么逆，于是这两题都采用乘法逆元的方法去解

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int i; // [rsp+4h] [rbp-ACh]
  int v5; // [rsp+8h] [rbp-A8h]
  __int64 c[5]; // [rsp+10h] [rbp-A0h]
  int v7; // [rsp+38h] [rbp-78h]
  char v8; // [rsp+3Ch] [rbp-74h]
  char input[8]; // [rsp+40h] [rbp-70h] BYREF
  __int64 v10; // [rsp+48h] [rbp-68h]
  __int64 v11; // [rsp+50h] [rbp-60h]
  __int64 v12; // [rsp+58h] [rbp-58h]
  __int64 v13; // [rsp+60h] [rbp-50h]
  __int64 v14; // [rsp+68h] [rbp-48h]
  __int64 v15; // [rsp+70h] [rbp-40h]
  __int64 v16; // [rsp+78h] [rbp-38h]
  __int64 v17; // [rsp+80h] [rbp-30h]
  __int64 v18; // [rsp+88h] [rbp-28h]
  __int64 v19; // [rsp+90h] [rbp-20h]
  __int64 v20; // [rsp+98h] [rbp-18h]
  int v21; // [rsp+A0h] [rbp-10h]
  unsigned __int64 v22; // [rsp+A8h] [rbp-8h]

  v22 = __readfsqword(0x28u);
  *(_QWORD *)input = 0LL;
  v10 = 0LL;
  v11 = 0LL;
  v12 = 0LL;
  v13 = 0LL;
  v14 = 0LL;
  v15 = 0LL;
  v16 = 0LL;
  v17 = 0LL;
  v18 = 0LL;
  v19 = 0LL;
  v20 = 0LL;
  v21 = 0;
  c[0] = 0x9F8E7A1CC6486497LL;
  c[1] = 0x69EEF382E760BD46LL;
  c[2] = 0xB9C017E2E30EF749LL;
  c[3] = 0x98410148A430392CLL;
  c[4] = 0xE80E7411E5B5A939LL;
  v7 = 0xA58BFDAC;
  v8 = 0x6D;
  fwrite("input: ", 1uLL, 7uLL, stdout);
  fgets(input, 46, stdin);
  if ( strlen(input) != 45 )
    exit(0);
  for ( i = 0; i <= 44; ++i )
  {
    v5 = 23 * input[i];
    if ( ((unsigned int)((v5 + x[i]) >> 31) >> 24) + (_BYTE)v5 + x[i] - ((unsigned int)((v5 + x[i]) >> 31) >> 24) != *((_BYTE *)c + i) )
      exit(0);
  }
  puts("good!");
  return 0;
}

注意的点

• 两此移位直接归0
• v5前的 (_BYTE)

写出等式直接解即可

23 * input mod 256 + x = c
d = invert(23, 256)
input = (c - x) * d mod 256

EZMATH

把dll拉进dnSPY64（好久没用了

using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

namespace EzMath
{
	// Token: 0x02000003 RID: 3
	public static class Checker
	{
		// Token: 0x06000005 RID: 5 RVA: 0x00002110 File Offset: 0x00000310
		public static byte[] Encrypt1(byte[] a)
		{
			List<byte> list = new List<byte>();
			for (int i = 0; i < 8; i++)
			{
				uint num = (uint)((ulong)utils.Unpack32(RuntimeHelpers.GetSubArray<byte>(a, new Range(4 * i, 4 * (i + 1)))) * 83987UL % (ulong)-232573883);
				list.AddRange(BitConverter.GetBytes(num));
			}
			return list.ToArray();
		}

		// Token: 0x06000006 RID: 6 RVA: 0x00002174 File Offset: 0x00000374
		public static byte[] Encrypt2(byte[] a)
		{
			List<byte> list = new List<byte>();
			for (int i = 0; i < 4; i++)
			{
				ulong num = utils.Unpack64(RuntimeHelpers.GetSubArray<byte>(a, new Range(8 * i, 8 * (i + 1))));
				ulong num2 = num ^ num >> 25;
				list.AddRange(BitConverter.GetBytes(num2));
			}
			return list.ToArray();
		}
	}
}

• 程序先经过 乘模加密 再经过 移位加密

• 那么逆回去就是先 移位解密 再 乘法逆元

EXP

于是写了自己和看了别人的，不同视角解题（慢慢学习struct包

from gmpy2 import invert
import struct

c = [218,49,230,35,65,168,134,53,233,62,212,208,127,224,63,164,36,88,65,138,118,255,107,22,16,239,61,58,130,101,227,109]

# Encrypt1    m * 83987 % -232573883
p = -232573883 & 0xffffffff
d = int(invert(83987, p))
def decrypt1(s):
    t = b''
    for i in range(8):
        k = struct.unpack("<I", (s[i*4: i*4+4]))[0]
#        print(hex(k))
#        print(hex(k) + hex(d) + hex(p))
        k = k * d % p 
        t += struct.pack("<I", k)
    return t 

#Encrypt2    m ^ (m>>25)    a:25 b:25 c:14
def decrypt2(s):
    t = b''
    for i in range(4):
        k = struct.unpack("<Q", s[i * 8: i * 8 + 8])[0]
        ka = (k >> (25 + 14)) & 0x1ffffff # 完好的高25位
        kb = (k >> 14) & 0x1ffffff # 经过异或后的中25位 
        kc = k & 0x3fff # 底14位
        a = ka
        b = a ^ kb # 将高25位与中25位异或恢复高50位
        c = (b >> 11) ^ kc # 再把恢复后的25右移14位恢复低14位
        k = (a << (25 + 14)) | (b << 14) | c
        t += struct.pack("<Q", k)
    return t 

print(hex(d))
print(hex(p))
c = bytes(c)
c = decrypt2(c)
c = decrypt1(c)
print(c)
#28956fc4c54045a8808d42a5fab4b5f8
#Dest0g3{28956fc4-c540-45a8-808d-42a5fab4b5f8}   

c = [0] * 5
c[0] = 0x9F8E7A1CC6486497
c[1] = 0x69EEF382E760BD46
c[2] = 0xB9C017E2E30EF749
c[3] = 0x98410148A430392C
c[4] = 0xE80E7411E5B5A939
x = [0x7B, 0x51, 0xF3, 0x5A, 0xCC, 0x39, 0xF9, 0x92, 0x1C, 0x9E, 0x58, 0x69, 0x9D, 0xF7, 0xFD, 0x4A, 0x3E, 0xFB, 0x1D, 0x2C, 0x4D, 0x0C, 0x70, 0xB1, 0x3B, 0x8D, 0x25, 0xED, 0x91, 0xB1, 0x73, 0x8D, 0x82, 0xE6, 0xE7, 0x50, 0x20, 0x61, 0x62, 0x3C, 0x00, 0x3A, 0xA6, 0x9D, 0x32]
d = invert(23, 256)

dec = []
for t in c:
    dec += list(struct.pack("<Q", t))
dec += list(struct.pack("<I", 0xA58BFDAC))
dec.append(0x6D)

for i in range(0, len(dec)):
    print(chr((dec[i] - x[i]) * d % 256), end = "")

C版EZMATH

#include <stdio.h>
#include <stdint.h>

int main(void)
{
	int i, j;
	uint64_t enc[] = { 0x3586A84123E631DA, 0xA43FE07FD0D43EE9, 0x166BFF768A415824, 0x6DE365823A3DEF10, 0x12345671081F6A71 };
	uint64_t Hlow7 = 0x1234567812345678;
	
//	printf("%p\n", Hlow7 ^ Hlow7 >> 25);
//	
//	printf("%X\n", (unsigned int)-232573883);	
	for ( i = 0; i < 5; i++ )
	{
		enc[i] = ((enc[i] & 0xFE00000000000000) >> 25) ^ enc[i];
		enc[i] = ((enc[i] & 0x1FFFFFF00000000) >> 25) ^ enc[i];
		enc[i] = ((enc[i] & 0xFE000000) >> 25) ^ enc[i];
//		printf("0x%p, ", enc[i]);
	}
	
	
	unsigned int * t = (unsigned int *)enc;
	unsigned int encc[8];
	for ( i = 0; i < 8; i++ )
	{
//		printf("%X, ", t[i]);
		uint64_t x = t[i];
		unsigned int flag =  x * 0x9655fd32 % 0xf2233445;
		for ( j = 0; j < 4; j++ )
		{
			printf("%c", flag & 0xFF);
			flag >>= 8; 
		}
	}
	
	return 0;	
} 

GetFlag!