# How to reverse this hash function?

I have a function that takes an $m$ byte inputs $x_i$ and maps it a 32 byte outputs $y_j$. The hash function is defined as:

$$y_j = \sum_{i=1}^{m} (x_i)^{i-1} \pmod {127}$$

The input is restricted to the ASCII characters 'f' to 'u'. The input letters are in alphabetic order.

How can I recover the inputs $x_i$ given the outputs $y_j$?

I think you could calculate it manually or write code to solve this. You need to calculate X values from starting with end.

For example : $X_{32}$ = 84 = $X_{32}^{31}$ $mod_{117}$

When you get $X_{32}$ value then you can calculate $X_{31}$:

$X_{31}$ = 62 = $X_{31}^{30}$+$X_{32}^{30}$ $mod_{117}$

The only unknown value is $X_{31}$ here. You need to do this until u reach $X_1$ then all data would be decrypted.

You cannot uniquely invert it. Your hash will have the form $$y_1 \quad y_2 \quad \dots \quad y_m$$ with $y_i=\sum_{k=1}^m x_k^{i-1}.$ First look at the special case $m=2$. $y_1$ will always be $y_1=m=2,\,$ the other equation is $y_2=x_1 + x_2$. You cannot uniquely determine both $x_1,x_2$. In the general case you have $y_1=m$ and $m-1$ equations for the $m$ unknown entities $x_i$.

• Yeah, this problem can't be solved in unique way. – Raghu Dixit Apr 15 '16 at 21:03

Use the number of occurrences of each letter as the unknowns you're solving for. This gives you 32 linear equations to solve for 16 unknowns. Use standard approaches for solving systems of linear equations. Finally use the fact that the letters are ordered alphabetically to reconstruct the $x_i$ values.

• @RaghuDixit I'm no expert, but wouldn't standard approaches like Gaussian elimination work? Just make sure that you compute the scalar operations in the finite field and not over integers/reals. In particular make sure to use modular multiplicative inverses to compute divisions. – CodesInChaos Apr 14 '16 at 13:04