Results 1 to 6 of 6

Math Help - A cipher problem

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    6

    A cipher problem

    Consider the 26 letters of the alphabet together with the set of symbols {_, . , , , ;, :}
    to complete a 31-character alphabet. Associate a->0, b->1, ,z->25,_->26, .->27, ,->28, ;->29, and :->30. Consider all maps of the form:
    f(x) = ax + b mod 31.
    a) How many of these maps are invertible?
    b) Of those that are invertible, how many have no fixed points?
    c) Select a cipher with no fix points and encode with it the string:
    this_is,_i_believe,_a_secure_cipher.
    d) Compute the inverse of the cipher selected in c) and use it to decode the string
    e) Devise a method for deciphering a string encoded with this cipher. Test it with the
    encoded string.

    how do you find how many maps are invertible, what are maps??
    I really dont understand any of these questions any help plz
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Examples of maps

    Here's a simple map: a=1, b=0, so f(x) = x(31). That means you would encode the word "math" to m->m, a->a, t->t, h->h, or in other words your coded word is "math". Clearly this isn't a good way to hide information.

    Let's try a more complicated map: a=1, b=1, so f(x) = x+1(31). Now "math" -> "nbui". This is better in that someone reading the word "nbui" wouldn't immediately recognize this as the word "math.

    Can you keep going?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by ps1313 View Post
    ...
    Consider all maps of the form:
    f(x) = ax + b mod 31.

    a) How many of these maps are invertible?

    b) Of those that are invertible, how many have no fixed points?

    c) Select a cipher with no fix points and encode with it the string:
    this_is,_i_believe,_a_secure_cipher.
    d) Compute the inverse of the cipher selected in c) and use it to decode the string
    e) Devise a method for deciphering a string encoded with this cipher. Test it with the
    encoded string.

    how do you find how many maps are invertible, what are maps??
    I really dont understand any of these questions any help plz
    a) The modulus is 31, which is prime: ALL of the maps are invertible.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    Quote Originally Posted by aidan View Post
    a) The modulus is 31, which is prime: ALL of the maps are invertible.

    Let's suppose a=0 and b arbitrary, so that \forall x \in X is f(x)=b...

    ... are You sure that it is allways possible to recovery x in such a case? ...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The map that allows to find, given a plaintext character x , the corresponding chiphertext character k=f(x) is...

    k=ax+b \mod 31 (1)

    From (1) we derive the dechipering law...

    x= a^{-1} (k-b) \mod 31 (2)

    ... where a^{-1} is the multiplicative inverse of a. From (2) we derive immediately that the (1) is invertible if and only if a^{-1} exists, and, because 31 is prime, that is verified if a\ne 0 \mod 31. The overall number of invertible codes is the 30\cdot 31= 930...

    The second question is about the requested property of the cipher code to don't have 'fixed points', i.e. any value of x for which is k(x)=x. At this scope will be useful the following table, where are represented the multiplicative inverse of any a\ne 0 \mod 31...

    1^{-1}=1,2^{-1}=16,3^{-1}=21,4^{-1}=8,5^{-1}=25,6^{-1}=26,

    7^{-1}=9,8^{-1}=4,9^{-1}=7,10^{-1}=28,11^{-1}=17,12^{-1}=13,

    13^{-1}=12,14^{-1}=20,15^{-1}=29,16^{-1}=2,17^{-1}=11,18^{-1}=19,

    19^{-1}=18,20^{-1}=14,21^{-1}=3,22^{-1}=14,23^{-1}=27,24^{-1}=22,

    25^{-1}=5,26^{-1}=6,27^{-1}=23,28^{-1}=10,29^{-1}=15,30^{-1}=30

    From (1) we derive the condition for x to be a fixed point...

    x=ax+b \mod 31 \rightarrow x=(1-a)^{-1} b \mod 31 (3)

    From (3) we derive that there are no fixed points if and only if is...

    a=1 \mod 31, b\ne 0 \mod 31 (4)

    The overall numer of 'no fixed points' codes is [only] 30...

    A code expressed by the chipering law k=x + b \mod n is commonly called 'Caesar's code' because Julius Caesar first used it. Certainly the security of such type of cose was adequate for Caesar when he faught against Celtics and Britishers... today it is much less reccomandable ...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by chisigma View Post
    ... are You sure that it is allways possible to recover x

    \chi \sigma
    Thanks for clearing that up.

    I thought about that while driving & realized that "a" could assume a value of zero -- thus impossible to recover the original!

    Sorry for the short sightedness.

    ---
    "fixed point" is a terrible description for what it describes. A much better definition would be "static node"

    The problem above is commonly called "as affine cipher."
    Last edited by aidan; November 30th 2009 at 11:03 AM. Reason: added note
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Exponential cipher
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 10th 2011, 11:42 AM
  2. affine cipher
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 25th 2010, 05:09 AM
  3. Simple cipher
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 08:06 AM
  4. A Cipher
    Posted in the Math Puzzles Forum
    Replies: 4
    Last Post: December 6th 2009, 07:48 PM
  5. Hill Cipher Problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 10th 2006, 10:58 AM

Search Tags


/mathhelpforum @mathhelpforum