flat assembler
Message board for the users of flat assembler.

 Index > Main > reversing a modolus?
Author
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 02 May 2006, 00:30
Code:
```9 = B8 mod 19

B8 / 19 = 7
(19 * 7) + 9 = B8    ```

Let's say I do this: B8 Mod 19 and get 9..... What is the fastest possible way to calculate that B8 back ......having only the outcome of B8 Mod 19 (9) and the number B8 was moded with?
My solution is up there however, its a bit costly in cycles
02 May 2006, 00:30
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 03 May 2006, 07:53
I'm not sure that I understood you correctly...
Do you mean that you have numbers 9 and 19 and you want to find X, where X mod 19 = 9?
If so then there is not only B8 which will give you 9 when moded with 19. What operand sizes are used? One byte only?
03 May 2006, 07:53

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 03 May 2006, 08:26
Simple answer: you can't!

You only know B8%19 and 19, but you don't know B8 neither 7. You have to know at least one of them.

When you've got 9 and 19 then the B8 can be anything from 9, 28, ... to 19*n+9.

For the solution - if you have the neccessary variables - yours is correct and not very costy in cycles.
03 May 2006, 08:26
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 03 May 2006, 18:49
Ok in decimal not in hex my solution works.

a mod b = c

a = [(b * (a/b)] + (c) " without the remainder of a/b

Ex : 99 mod 19 = 4

99 = (19*(a/b)) +4

Hwoever I dont have a
03 May 2006, 18:49
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 03 May 2006, 19:17
Im using an encryption for a program based on modolus .. And I need a way to find a..... This is the only way I have .... But with a... But in the program I won't be able to have a
03 May 2006, 19:17
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 03 May 2006, 19:43
Code:
```19 mod 19 = 0
20 mod 19 = 1
21 mod 19 = 2
22 mod 19 = 3
23 mod 19 = 4
24 mod 19 = 5
25 mod 19 = 6
26 mod 19 = 7
27 mod 19 = 8
28 mod 19 = 9
29 mod 19 = 10
30 mod 19 = 11
31 mod 19 = 12
32 mod 19 = 13
33 mod 19 = 14
34 mod 19 = 15
35 mod 19 = 16
36 mod 19 = 17
37 mod 19 = 18
38 mod 19 = 0
39 mod 19 = 1
40 mod 19 = 2
etc etc.....
```

It will keep going like this.....
03 May 2006, 19:43
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 04 May 2006, 07:13
One of the properties of congruences is symmetry, that's:
if a = b (mod m), then b = a (mod m).
Things are very simple when m = 2. It's just XOR, you know.
But if modulo != 2 than you cannot do it in just a few cycles. The simplest solution that comes to my mind right now is:
1. convert numbers to base m (19 in your example)
2. apply XOR equivalent to them.
3. conevrt back to base 2 (or 16 - it doesn't matter).

or you can work with "base m" numbers all the time. some math functions should be implemented then. But I cannot give the optimal solution at this time. The proplem is interesting and i'll think of it for sure... when I have time.

visit http://mathworld.wolfram.com/.
04 May 2006, 07:13
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 04 May 2006, 07:23
BTW, you'll have more than one solution of this problem. Maybe selecting the minimum one (or, for example, the second from the mininum) for the chosen operand size is the way to avoid errors when decipher.
04 May 2006, 07:23
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 04 May 2006, 09:48
I was trying to solve the problem, but was confused a bit. But now I think I've got the idea of what you wanna do. Is it a multiplicative cipher you're trying to implement? Please, provide the community with your algorithm

If it is so, then the simplest form of a multiplicative cipher is:
encipher: ciphertext=msg*key (mod m)
decipher: msg=ciphertext*(1/key) (mod m)

to find 1/key (mod m) you should use Eucledian algo. I can provide you with formulas to implement it... if you need.
04 May 2006, 09:48
Vasilev Vjacheslav

Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav 04 May 2006, 10:07
zhak, we will be very appreciate for this formulas, i am also interested in this problem
04 May 2006, 10:07
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 04 May 2006, 23:07
(input mod key)-0C4h)

This is what Im using

I really can't solve it sigh...

Last edited by shism2 on 04 May 2006, 23:23; edited 1 time in total
04 May 2006, 23:07
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 04 May 2006, 23:10
I believe it's only possible by a bruteforce of such
04 May 2006, 23:10
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 05 May 2006, 18:30
Vasilev Vjacheslav, here's how to find 1/a (mod b)

05 May 2006, 18:30
shism2

Joined: 14 Sep 2005
Posts: 248
shism2 05 May 2006, 19:03
So do you have a solution for my problem?
05 May 2006, 19:03
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum