纠结着我的难题——一个密码的相关算法

silitex · 发表于 2010-10-19 16:09:49

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

大家好，今天被一个密码算法给纠结住了，在这里顺便请教大家：
已知：
  1. x, c, r为4字节正整数(DWORD类型)，
  2. (x*c)%0x100000000 = r (0x100000000为16进制数，且为DWORD的最大数值加1，即0xFFFFFFFF+1)
  3. c一般为奇数，且0x100000000%c != 0
  4. 现在如果已经知道c和r的值，x值未知
  5. 在我现在项目中，c已经是一个固定值0x11FA73B(16进制), 但r的值为任意值，
  6. 我的难题：怎样才可以快速求出x的值？
望得到大家的提示！谢谢！

gxqcn · 发表于 2010-10-19 16:24:35

x ≡ r*c^-1=0xFFE699F3 * r (mod 2³²)

silitex · 发表于 2010-10-19 16:36:18

x ≡ r*c-1=0xFFE699F3 * r (mod 232)
gxqcn 发表于 2010-10-19 16:24

确实太高明了！经过验证了两个，都是正确的。
能否问问：0xFFE699F3 这个数值是怎样求出来的？

gxqcn · 发表于 2010-10-19 16:43:08

我用 HugeCalc 计算 c 关于 2^32 的模逆，即可得到该常数。
模逆的计算通常可用扩展GCD算法实现，或用本论坛曾讨论过的：快速求大整数关于 2^n 的模逆

账号		自动登录	找回密码
密码			欢迎注册

[提问] 纠结着我的难题——一个密码的相关算法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。