Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers. Consider posting your question at Cryptography.SE.

learn more… | top users | synonyms (2)

1
vote
1answer
60 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
79 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
53 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
28 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 ...
0
votes
1answer
19 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
47 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
56 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. ...
0
votes
1answer
137 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 ...
1
vote
1answer
26 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 ...
2
votes
0answers
67 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
66 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
1answer
169 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. ...
1
vote
0answers
371 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 ...
0
votes
2answers
62 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
46 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, ...
3
votes
1answer
162 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
20 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: ...
0
votes
0answers
34 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
0
votes
0answers
26 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
42 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
37 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
43 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?
3
votes
3answers
347 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 ...
0
votes
1answer
35 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 ...
1
vote
1answer
60 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 ...
1
vote
0answers
185 views

Does there exist some relations between Cryptography and Algebraic Topology?

We know that there are many application of Cryptography in our real life. Are there any relation between Cryptography and Algebraic Topology? If yes, please suggest me some link or books. Thanks ...
1
vote
0answers
53 views

provably secure hash function

I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows: Gen: on input $1^n$, run to obtain ...
0
votes
1answer
115 views

solving mod equation

I am attempting to solve $r_1$ in this equation: $$m + xr \equiv m_1 + xr_1 \pmod q$$ This is what I derived at: $$m-m_1 + xr / x \equiv r_1 \pmod q$$ I proceed to sub these with the necessary ...
1
vote
1answer
31 views

Are bit permutations linear?

I'm trying to answer a question on cryptography. Basically, inputs and outputs (so plaintexts and ciphertexts) are from the set (say) $\{0, 1\}^{100}$. The encryption function takes inputs and splits ...
2
votes
1answer
98 views

Cryptography, discrete mathematics

I have got following example at the lecture, however we went through it quite fast. I understand the calculation of the following inverse modulo: 7 · 103 = 1 (mod 120). However here I am puzzled ...
1
vote
1answer
54 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 ...
3
votes
0answers
79 views

Evaluate a rational function at infinity

In the context of the Tate pairing, I would like to know that it means to `evaluate' an $\mathbb{F}_{q^k}$-rational function at $\infty$. For instance, the reduced Tate pairing is $e_n:G_1\times ...
0
votes
1answer
126 views

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ I need to find $x$ using the Pohlig-Hellman algorithm.
-1
votes
1answer
39 views

NTRU cryptosystem

For the NTRU cryptosystem (as described here http://en.wikipedia.org/wiki/NTRUEncrypt), why is it really easy for Eve to decrypt if $p$ divides $q$. My answer was that when Eve sees $e(x)= ...
1
vote
2answers
35 views

Undoing anonymous donations

All the students in a class are planning to do a trip. Not all of the students can afford it, and it is considered shameful to reveal their poverty. So it is suggested that anyone can donate ...
0
votes
1answer
30 views

How is it possible to write $\text {Pr} [M = m]$ where $M$ is random variable defined over a message space $\mathcal M$ and $m \in \mathcal M$.

In cryptography we consider random variables $K, M$ and $C$ over the key space $\mathcal K$ , message space $\mathcal M$ and cipher space $\mathcal C$, respectively. I've studied discrete mathematics ...
0
votes
1answer
49 views

NTRU cryptosystem

In the NTRU cryptosystem we are dealing with convolution polynomial rings and we compute $f(x)= T(d+1,d)$ and $g(x)= T(d,d)$ but when calculating their inverse in $R_q=(Z/qZ[x] / (x^N-1))$ and ...
1
vote
0answers
39 views

Find a polynomial of degree $8$ with integer coefficients with given root

algorithm to find a polynomial $f(x)$ s.t (1) $degree(f(x))<9$ (2) Integer coefficients (3) Absolute value of coefficients $< 10^5$ (4) f(39.770525) =~ 0 about to be <<10^-10 I ...
0
votes
1answer
26 views

Why in cryptography it is common to use the SAME key for all the group?

I believe that it is safer that each member should have his or her encryption and decryption keys that no one else knows. IN this case a message $m$ is sent as $m^{e_1}$ the receiver sends $t$ back as ...
0
votes
2answers
40 views

Continuous trapdoor functions?

Every trapdoor function I've seen has been a discrete function. Do there exist continuous trapdoor functions? If so, what's an example of a continuous trapdoor function? And if not, why not?
0
votes
1answer
48 views

Cryptography question

I think this is a pohlig hellman symmetric key system working in $\mathbb{Z}/p\mathbb{Z}$ Assuming Alice and Bob both have p (a prime) and k (a key) If Alice sends $m^k$ to Bob, can Bob raise $m^k$ ...
0
votes
0answers
34 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
1
vote
4answers
195 views

Elliptic curves (sum and multiply)

I was wondering if someone could give me some resources on elliptic curve cryptography. Specifically I need to know how to do something like: $y^2=x^3-x+1$ compute $(0,1)⊕(1,1)$ or $y^2=x^3+x^2-x$ ...
0
votes
0answers
44 views

Elliptic curve cryptography order

How do I compute an order a a point P on an elliptic curve? My question is specifically in reference to the attached photo. I understand how to do part a but I am totally lost in part b. I don't know ...
1
vote
1answer
28 views

Modular equation with non-integer numbers?

I was reading the book Homomorphic Encryption and Applications when I saw a modular equation involvind non-integer numbers. In short, on page 59 the book define the set $y$ as $\{y_1, y_2, .., ...
1
vote
1answer
31 views

Elliptic curves: Can I replace a coordinate with any modularly equivalent number?

I have a point (x, y) in an elliptic curve group. Suppose y is negative. Can I rewrite it as a positive number if that positive number is equivalent to y (modulo the characteristic of the group)? ...
0
votes
1answer
83 views

El Gamal encryption/decryption

First of all I want to ask if I did part a correctly? Alice has two secrets, $s_1 = 55$ and $s_2 = 108$ and wants to communicate one of them to Bob without knowing which one. Alice and Bob agree to ...
2
votes
1answer
78 views

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$. I've always done matrix arithmetic in a field $\mathbb F$ and that is what ...