A cipher problem

**ps1313** · November 29th 2009, 06:45 AM

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

**qmech** · November 29th 2009, 07:10 PM

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?

**aidan** · November 29th 2009, 09:23 PM

Originally Posted by ps1313

...
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.

**chisigma** · November 29th 2009, 11:00 PM

Originally Posted by aidan

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$

**chisigma** · November 30th 2009, 04:03 AM

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$

**aidan** · November 30th 2009, 10:55 AM

Originally Posted by chisigma

... 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."

Thread: A cipher problem

LinkBack

Thread Tools

Display

A cipher problem

Examples of maps

Similar Math Help Forum Discussions

Exponential cipher

affine cipher

Simple cipher

A Cipher

Hill Cipher Problem

Search Tags