Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

learn more… | top users | synonyms (2)

1
vote
2answers
24 views

Help with linear recurrence.

I am trying to understand the following problem: Consider the following linear recurrence over $Z_2$ of degree four: $z_{i+4} = (z_{i+3} + z_{i+2} + z_{i+1} + z_{i}) \bmod 2$ i >= 0. ...
0
votes
1answer
27 views

Stream ciphers - Block ciphers

What is the difference between the stream ciphers and the block ciphers?? Is the difference the time complexity?? At the block ciphers the message is cut into parts of $n$ characters. If we have ...
0
votes
1answer
34 views

Who to solve this linear modular equation system?

I have this equation system: a + b + c (mod 11) = 8 9a + 3b + c (mod 11) = 2 16a + 4b + c (mod 11) = 9 Unfortunately I totally don't know how to solve it. It is in general part of Lagrange's ...
3
votes
2answers
73 views

In cryptography, why do we reduce elliptic curves over finite fields?

What's wrong with real numbers? Is the continuous logarithm problem "easy" to solve for elliptic curves? Here's what I believe: elliptic curves over the real numbers have infinitely many points, many ...
0
votes
0answers
71 views

Find a point $P$ on an elliptic curve, given $2P$

Let $E$ be the Elliptic curve given by $Y^2=x^3+5x-6$ and suppose $P$ is a point on $E$ over $\mathbb F_{65537}$ with $2P=(7283,24272)$. Find $P$. I approached this question as follows. ...
0
votes
2answers
62 views

Function for encryption/decryption - What is $n \phi(n)$?

In my notes there are the following functions of encryption/decryption: $$E_k(x)=x+k$$ $$D_k(y)=y-k$$ ($E_k : \mathbb{Z}_n \rightarrow \mathbb{Z}_n$) ($D_k : \mathbb{Z}_n \rightarrow ...
0
votes
1answer
32 views

How many multiplications are needed when one applies the algorithm to computing $132^{1023} \mod 2047$?

Suppose the integer $a$ has binary representation $b_kb_{k-1}\cdots b_1b_0$ where $b_i$ are either $0$ or $1$. The power $x^a \mod n$ can be computed using the fast exponential algorithm. The ...
0
votes
2answers
55 views

Where does 2525 and 252525 come from in RSA cryptosystem example?

This is an example from Discrete Mathematics and its Applications I understand how to encrypt, the first step is to turn the letters into their numerical equivalents(same thing we had to do for ...
0
votes
1answer
21 views

How to recover the original text/find decryption function?

This is from Discrete Mathematics and its Applications Here's my book section on shift ciphers. I understand the idea behind this. If you were trying to encrypt say a single letter 'b' with a ...
1
vote
4answers
77 views

How to prove this modular multiplication property to be true?

I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90 Here is author's work In this problem, the author was trying to calculate $5^{40}$ He worked ...
6
votes
3answers
125 views

Is this proof for $(\mathbb{Z},+) \ncong (\mathbb{Q},+)$ valid?

In an introductory cryptography course, our teacher demonstrated a proof for $(\mathbb{Z},+) \ncong (\mathbb{Q},+)$. I'm not convinced, even though the statement may be correct (I don't know). ...
2
votes
1answer
46 views

Generating elements of a Galois Field using an irreducible polynomial

I am practicing some cryptography problems and I am having problems with one involving Galois Fields and irreducible polynomials. Here is the problem: Using the irreducible polynomial $f(x) = x^5 ...
0
votes
0answers
22 views

Verify no elements of a list have been removed

I have an sequence of $k$ elements, $\{a_k\}$. Say at any given moment I add an element $a_{k+1}$ to the sequence. Is there any way to verify the sequence has not been altered, without checking each ...
1
vote
1answer
53 views

Finding the Order of a group and the Order of each element

I am working on a cryptography example problem. The problem is the following: For the group G = < Z26*, x> a) find the order of the group b) find the order of each element in the group c) Is ...
1
vote
1answer
56 views

Suppose that you had a machine that could find all four solutions for some given $a$. How could you use this machine to factor $n$?

Question: Suppose $n = pq$ with $p$ and $q$ distinct odd primes. Suppose that you had a machine that could find all four solutions for some given $a$. How could you use this machine to factor $n$? ...
2
votes
1answer
61 views

Prove that if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, then it has four solutions.

Question: Suppose $n = pq$ with $p$ and $q$ distinct odd primes. Suppose that gcd($a,pq$) = 1. Prove that if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, then it has four solutions. ...
0
votes
0answers
43 views

Elliptic Curve finding point of a curve backward?

Given $E: y^2=X^3+5X-6$ over $F=(65537)$ with $2P=(7283, 24272)$ how to find $P$ Can anyone provide an example in steps?
0
votes
1answer
23 views

Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...
1
vote
1answer
68 views

Finding the Modular Multiplicative Inverse of a large number

I am practicing some modular arithmetic and I am trying to find the multiplicative inverse of a large number. Here is the problem: 345^-1 mod 76408 I'm not sure how to go about solving this problem. ...
0
votes
1answer
57 views

Given an encryption key in a transposition cipher, find the decryption key

I am continuing my practice on problems for my cryptography class. I'm starting to get the hang of basic ideas of ciphers. At least i thought this until I attempted to do the follwng problem: The ...
0
votes
1answer
17 views

Cryptographic encoding scheme that enables counting

Suppose there are $n$ players. Each player has a $k$-length bit vector. Is there an efficient way of encoding the $k$ length bit vectors, such that after receiving the $n$ encoded outputs, one can ...
1
vote
1answer
37 views

Proving that a set Rn (relatively prime with respect to any n) is a group

Question: prove that the set of all Rn (relatively prime with respect to any n) is a group ... there is a theorem that states Rn is a group for n > 0, but i dont know where that came from... (Just ...
1
vote
1answer
41 views

$a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even

Questions: Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that $a$ has a square root modulo $p$ if and only if its discrete logarithm log$_{g}(a)$ modulo $p - 1$ is even. ...
1
vote
1answer
24 views

Finding all the solutions of a linear equations

I am trying to find all the solutions to the following equation: $5x \equiv 15\pmod{25}$ Here is what I've done: Find the $\mathrm{gcd}(5,25) = 5$; there will be $5$ solutions. Divide the original ...
0
votes
2answers
96 views

Why is it safe to assume $M$ is less than all $N$s in Håstad's Broadcast Attack

I am reading the Wikipedia article on Broadcast attack. In the proof, the editor made an assumption that $M$ is less than all $N$. Why is this assumption safe?
2
votes
0answers
34 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
1
vote
1answer
62 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
1
vote
0answers
116 views

Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and ...
3
votes
4answers
695 views

how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
5
votes
2answers
360 views

RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
0
votes
2answers
58 views

Understanding why the public exponent $e$ is chosen the way it is in RSA

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities ...
1
vote
1answer
37 views

Decrypting an Affine Cipher with Modulus

I'm trying to decrypt the ciphertext vczkh which I know was encoded using an affine cipher with the equation 7x + 8(mod 26). This makes my decryption function p = (c – b) * a^-1 (mod 26) where b = 8, ...
1
vote
1answer
77 views

What books do you recommend on mathematics behind cryptography?

I am currently reading the Book Understanding Cryptography from Cristof Paar. I am enjoying the book but i don't like to scratch the surface when it comes to cryptography. I would like do dig a little ...
0
votes
1answer
32 views

Reversible modular exponent in cryptography

I know this is possible from working code, but I can't wrap my head around how. For the given equation: $b = x^p\bmod\text{public_key}$ Where $p$ is prime ($131$ in my case). How to compute a ...
0
votes
1answer
13 views

Identify encryption scheme - possibly DSA or Diffie Hellman - only client shares key

I could use a hand in identifying the encryption scheme used in this scenario. (Its from source code known to work) There is a client connecting to a server such that: ...
2
votes
1answer
410 views

Prove: b passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$

Question: Let $p$ be a prime and $b$ an integer with $\gcd(b,p) = 1$. Prove: $b$ passes the Fermat test for $m = p^2$ if and only if $b^{p-1}\equiv 1\pmod {p^2}$. I know that if $b^{p-1}\not\equiv ...
0
votes
0answers
30 views

Rabin cipher question

I am getting wrong answer to this question. Any one else too has solved it ? Decrypt the Ciphertext message 1819 0459 0803 that was encrypted using the Rabin Cryptosystem with b= 3 and n= 47 *59
3
votes
3answers
338 views

Encryption with large mods

I am studying for a cryptography final and I have come across something I can just not figure out. My math background is rather weak. This is related to RSA and concerns itself with raising numbers ...
1
vote
2answers
119 views

What is an embedding degree of elliptic curve?

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am ...
0
votes
1answer
258 views

Modular multiplicative inverse in RSA

I been reading the wiki article about Modular multiplicative inverse and I don't understand it. Can you explain it to me in better way. To be more specific I am trying to understand the RSA algorithm ...
0
votes
0answers
22 views

1-2 Oblivious Transfer and its simulation by ordinary OT

The version of 1-2 oblivious transfer mentioned in Even, Goldreich and Lempel [1985] has the provision that the receiver, Bob, can discover with probability > 1/2 if the sender, Alice, sends the same ...
0
votes
0answers
22 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
0
votes
1answer
32 views

Factors of the RSA modulus

In the article "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
0
votes
2answers
36 views

Find all primes different from three for which $(3|p)=1$

Find all primes different from three for which $(3|p)=1$, where $(3|p)$ denotes the Ligendre symbol.
0
votes
0answers
19 views

What's the implication of the Frobenius automorphism to DLP

Given a field, e.g. GF(p^x), does the existence of a Frobenius automorphism affect the difficulty of calculating the discrete log in that field? How about other morphisms?
2
votes
1answer
112 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
0
votes
1answer
27 views

RSA decryption where e=3 m=12

I have a problem with RSA Decryption, if I set $n=3*11=33$ I get $\varphi(33)=20$ and e=3 the first problem is encrypting the Message 12, when I encrypt $12^3\equiv 12 (mod 33)$ meaning the the ...
2
votes
1answer
52 views

Textbook RSA game with one prime

Let p be a n-bits prime number, that is drawn uniformly. Let e and m uniformly drawn from Z(p-1) and Z*(p) respectively. Let y= (m^e) mod p Prove that the probability to find m while knowing only ...
26
votes
3answers
30k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
1
vote
1answer
45 views

RSA Encryption (Block division)

I have a fair idea of what RSA encryption is and how to do it, but I don't quite understand the following bit given in my textbook: I have an exam tomorrow and I'm expected to encrypt a string of ...