Results 1 to 5 of 5

Math Help - cryptography help

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    cryptography help

    1) Your RSA public key is n=115. Bob sends you an encrypted letter of
    the alphabet, which he encrypted by cubing it modulo n.
    The transmission you received from Bob is 03. Use your decryption key
    to figure out what letter of the alphabet Bob sent you.

    2) Alice's RSA public key is n=1050589. Bob wants to send her a message consisting of one letter
    of the alphabet together with some nonsensical padding. (The padding could be anywhere in the message.)
    Bob encrypts his message by cubing it modulo n. By eavesdropping, you discover that
    the transmission Alice receives from Bob is 306720. Using the knowledge that Alice carelessly
    chose her two primes too close together, crack her RSA code, and then figure out what letter of the alphabet
    Bob sent to her in his message. (Crack the code means find her decryption key.)
    Hint: To simplify the computations, I chose 306720 so that its order mod n is only 10.
    You may use a calculator for this problem (e.g., the Google calculator).

    3) Let a and b be (congruent to) squares mod p, and let c and d be (congruent to) nonsquares mod p,
    where p is an odd prime not dividing abcd. (For example, if p=7, then a could be 23 and b could be 11
    and c could be 12 and d could be 13.) In general, which of the following are always squares mod p,
    and which of the following are always nonsquares mod p?
    (i) ab (ii) ac (iii) cd
    Justify.
    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 padsinseven View Post
    1) Your RSA public key is n=115. Bob sends you an encrypted letter of
    the alphabet, which he encrypted by cubing it modulo n.
    The transmission you received from Bob is 03. Use your decryption key
    to figure out what letter of the alphabet Bob sent you.
    So n=115=5 \cdot 23=pq
    p=5; q=23

    Because he cubes the message he wants to send, e=3.
    (n,e) is the public key.
    C=3, it's the coded message you receive.
    M is the message he sent.

    Hence, we have C=M^e \mod n

    Let d be such that ed= 1 \mod \varphi(n)

    C^d=M^{ed} \mod n = M \mod n (you should know that..)

    So if you want to get M, calculate C^d modulo n.
    ~~~~~~~~

    Calculating d :

    3d \equiv 1 \mod \varphi(115)
    \varphi(115)=4 \cdot 22=88

    We know that 3 \cdot 29=87=-1 \mod 88
    Therefore, 3 \cdot (-29)=1 \mod 88

    -29=59 \mod 88

    So \boxed{d=59}

    ~~~~~~~~

    M=C^d \mod 115

    C^d=3^{59}

    Either you use a calculator, either you do it by hand. I've tried parts but this yields to numbers I don't like and that are not kind to deal with...


    This looks like a draft, but I just tried to make it the simpliest way xD
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    4

    cryptography exercises/equations [help needed]

    Good evening,

    I have two exercises that I'm stuck with at the cryptography course

    1)first one I've reached a good point (it's probably almost finished)
    this is what I have :

    30^30 = 1 (mod31)

    I have to prove that this equation is true.

    2)here is the second exercise:

    Prove that the following is true: 11^n + 5^n = 0 (mod7) when n = 3 (mod6)
    Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)


    Many thanks in advance to anyone who spends time reading and trying to help, it means a lot, thank you.
    Last edited by closebelow; May 21st 2008 at 02:17 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by closebelow View Post
    Good evening,

    I have two exercises that I'm stuck with at the cryptography course

    1)first one I've reached a good point (it's probably almost finished)
    this is what I have :

    30^30 = 1 (mod31)

    I have to prove that this equation is true.
    Trivially follows from Fermats little theorem. He says a^p = a \text{ mod } p. So choose a = 30 and p = 31, we get 30^{31} = 30 \text{ mod } 31 \Rightarrow 30^{30} = 1 \text{ mod } 31
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    4
    Thank you very much for the help. I believe it is a reasonable solution.
    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. Cryptography....
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 09:20 PM
  3. Cryptography Help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2008, 11:17 AM
  4. Cryptography
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 19th 2008, 07:16 AM

Search Tags


/mathhelpforum @mathhelpforum