Results 1 to 4 of 4

Math Help - Trivial cryptography

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Trivial cryptography

    I'm trying to solve the task 3.13.2 (b) from the book "Introduction to Cryptography" by Wade Trappe & Lawrence Washington:

    Suppose you write a message as a number m (mod 31). Encrypt m as m^7 (mod 31). How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat's theorem will be useful.)

    Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by posix_memalign View Post
    I'm trying to solve the task 3.13.2 (b) from the book "Introduction to Cryptography" by Wade Trappe & Lawrence Washington:

    Suppose you write a message as a number m (mod 31). Encrypt m as m^7 (mod 31). How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat's theorem will be useful.)

    Any ideas?
    Fermat's theorem says that if p is a prime, m^p=m (\bmod p)

    So m^{31}=m (\bmod 31)
    And m^{30}=1 (\bmod 31)

    My thought is that you find a number in the form 30k+1 that is divisible by 7.
    For example 91=7x13.

    N^{13}=(m^7)^{13}=m^{91}=m^{30\times 3+1}=(m^{30})^3 \cdot m=m (\bmod 31)
    where N is the message you want to decrypt

    Not too sure if it's correct though
    Last edited by Moo; December 4th 2008 at 11:39 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Moo View Post
    Hello,

    Fermat's theorem says that if p is a prime, m^p=m (\bmod p)

    So m^{31}=m (\bmod 31)
    And m^{30}=1 (\bmod 31)

    My thought is that you find a number in the form 30k+1 that is divisible by 7.
    For example 91=7x13.

    N^{13}=(m^7)^{13}=m^{91}=m^{30\times 3+1}=(m^{30})^3 \cdot m=m (\bmod 31)
    where N is the message you want to decrypt

    Not too sure if it's correct though
    Thanks for the help, but I don't quite follow.

    So based on this then:

    e(m) = m^7 (mod 31)
    d(m) = m^13 (mod 31)

    Where e() is the encryption function and d() is the decryption function.
    If tested with m = 2 this seems to encrypt to 4 and then decrypt back to 2, ok.
    However I don't understand how you determined that it should be raised to the power of 13?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by posix_memalign View Post
    Thanks for the help, but I don't quite follow.

    So based on this then:

    e(m) = m^7 (mod 31)
    d(m) = m^13 (mod 31)

    Where e() is the encryption function and d() is the decryption function.
    If tested with m = 2 this seems to encrypt to 4 and then decrypt back to 2, ok.
    However I don't understand how you determined that it should be raised to the power of 13?
    The purpose is to find k such that (m^7)^k=m (\bmod 31)

    That is m^{7k}=m (\bmod 31)

    We know that m^{30}=1 (\bmod 31), thanks to Fermat's theorem.

    Hence for any integer j, we have (m^{30})^j=m^{30j}=1^j=1 (\bmod 31)

    Therefore, m^{30j+1}=m (\bmod 31)

    So it is sufficient that 7k=30j+1

    Find by trial and error that if j=3, then k=13.
    And this k is your decryption key.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cryptography
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 13th 2010, 04:59 PM
  2. Need help with Trivial/Non trivial solution
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 6th 2010, 05:53 AM
  3. Cryptography....
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 09:20 PM
  4. Trivial/Non Trivial Solutions
    Posted in the Advanced Algebra Forum
    Replies: 14
    Last Post: October 15th 2008, 05:17 PM

Search Tags


/mathhelpforum @mathhelpforum