flat assembler
Message board for the users of flat assembler.

Index > Main > reversing a modolus?

Author
Thread Post new topic Reply to topic
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
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
Post 02 May 2006, 00:30
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
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?
Post 03 May 2006, 07:53
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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.
Post 03 May 2006, 08:26
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
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 Sad
Post 03 May 2006, 18:49
View user's profile Send private message Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
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
Post 03 May 2006, 19:17
View user's profile Send private message Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
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.....
Post 03 May 2006, 19:43
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
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/.
Post 04 May 2006, 07:13
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
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.
Post 04 May 2006, 07:23
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
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 Smile

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.
Post 04 May 2006, 09:48
View user's profile Send private message Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
zhak, we will be very appreciate for this formulas, i am also interested in this problem
Post 04 May 2006, 10:07
View user's profile Send private message Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
(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
Post 04 May 2006, 23:07
View user's profile Send private message Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
I believe it's only possible by a bruteforce of such
Post 04 May 2006, 23:10
View user's profile Send private message Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
Vasilev Vjacheslav, here's how to find 1/a (mod b)


Description:
Download
Filename: modarithm_0v1.pdf
Filesize: 16.7 KB
Downloaded: 178 Time(s)

Post 05 May 2006, 18:30
View user's profile Send private message Reply with quote
shism2



Joined: 14 Sep 2005
Posts: 248
shism2
So do you have a solution for my problem?
Post 05 May 2006, 19:03
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.