• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Encryption Math - Inverse question.

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
condory
Just Arrived
Just Arrived


Joined: 16 Aug 2009
Posts: 0


Offline

PostPosted: Sun Aug 16, 2009 1:33 pm    Post subject: Encryption Math - Inverse question. Reply with quote

Hello, I would like to know how to calculate the inverse of each element in: Group Z*11?

The elements are: {1,2,3,4,5,6,7,8,9,10}, but how do u get the inverse?
Back to top
View user's profile Send private message
mah$us
Just Arrived
Just Arrived


Joined: 25 Feb 2009
Posts: 0


Offline

PostPosted: Sun Aug 16, 2009 4:59 pm    Post subject: Reply with quote

Probably you already know this, but for review:

In a group with operator o, the identity element e is the element with the property a o e = e o a = a. In a group like Z*11, where o is integer multiplication, e = 1.

The inverse of any element a is element b such that a o b = b o a = e.

In a small modular group like Z*11, it is easy to find the inverses by trial an error. For example, to find the inverse of 9:

9 * 2 = 18 = 7 (mod 11)
9 * 3 = 27 = 5 (mod 11)
9 * 4 = 36 = 3 (mod 11)
9 * 5 = 45 = 1 (mod 11) BINGO!

So the inverse of 9 in Z*11 is 5, and automatically we know also the the inverse of 5 is 9.

Obviously, this is infeasible for the enormous finite groups (Z*p where p is hundreds of decimal digits) used in real cryptosystems. It so happens that the sequence of divisions used in Euclid's algorithm to find the greatest common divisor gcd(p, a), where a is an element of Z*p, can be used to compute the inverse. Of course, the primary result of the gcd computation will be 1, because if a were not coprime to the modulus, no inverse would exists. But the steps of division that lead to that remainder of 1 enable computation of the inverse (if an inverse exists, that is, if element a is coprime to the modulus).

In Z*p, because p is prime, EVERY integer from 1 to p-1 is coprime to p, so all of these integers are members of the group, so |Z*p| = p-1. It is quite different for composite moduli - for example, Z*24 = {1, 5, 7, 11, 13, 17, 19, 23}. [This group also has the curious property that every element is its own inverse, so every element of Z*24 is a square root of 1.]

There is more than one way to use Euclid's algorithm to get the inverse. The oldest method uses a kind of back-tracking: starting with the last quotient, you can work backwards through the divisions. Several clever algorithmic variants of Euclid have been devised, which avoid this need for back-tracking. A good survey is at http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm. With a big integer library, you can program an extended euclidean function to compute modular inverses in just a dozen or so lines of code.
Back to top
View user's profile Send private message
condory
Just Arrived
Just Arrived


Joined: 16 Aug 2009
Posts: 0


Offline

PostPosted: Mon Aug 17, 2009 11:18 am    Post subject: Reply with quote

thank you, i understand it now. Very Happy
Back to top
View user's profile Send private message
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
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

Community Area

Log in | Register