Articles of cryptography

Computing square roots implies factoring $n = pq$

I’m proving that computing square roots in $\mathbb{Z}_{pq}$ implies factoring $n = pq$ with $p,q$ primes. The solution give you an algorithm: repeat 1. pick y from {1,…,n-1} 2. x = y^2 mod n 3. y’ = random square root of x until y’ != y and y’ != – y mod n Basically the […]

order of elliptic curve $y^2 = x^3 – x$ defined over $F_p$, where $p \equiv 3 \mod{4}$

It is said that the elliptic curve $y^2 = x^3 – x$ defined over a prime field $\mathbb{F}_p$, where $p \equiv 3 \mod{4}$ has an order $p + 1$. When I tried to get the elements of $E = \{(x,y) \in \mathbb{F}_3\times\mathbb{F}_3| y^2 = x^3 – x\} \cup \{\infty\} $, I only got 3 elements, […]

RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$

I want to determinate $p$ and $q$ in RSA. I know that $n = 172451$ and $\phi(n) = 171600$. $$171600 = pq – (p+q) + 1 = 172451 -(p + q) + 1$$ $$p + q = 172451-171600+1 = 852$$ $$(p-q)^2 = (p+q)^2-4pq = (852)^2 – 4(172451) = 36100$$ Now I’m stuck at this point […]

RSA: Creating a key of desired length

Thanks and with respect to the users of this site, I’ve succeeded in creating an Encryption/Decryption procedure for the RSA algorithm. I also implemented a Miller-Rabin probabilistic primality test. Now my question is much simpler, but my head really cannot make up an answer. Suppose I need a key of length 1024, and I’ve generated […]

pseudo-primality and test of Solovay-Strassen

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and : $$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$ Euler’s criterion states that if $n$ is not prime, then at most half of the elements $a$ in $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ are such that $n$ is $a$-pseudoprime. Now I would like to know if we can […]

Cracking Playfair code

I need to crack a Playfair encoded text without knowing the keyword. While searching the internet I found a way to do this using a ‘shotgun climbing hill’ method. Problem is, I can’t decide how to quantify one solution against the other. I’m pretty sure the text is in English. Any help would be appreciated. […]

Mental card game

Each of n persons draws a card from a shuffled deck of $k$ cards numbered from $1$ to $k$. There are at least as many cards as persons. The winner is the person who is holding the largest card. If everyone is honest, how can they mutually determine the identity of the winner, without any […]

What is necessary to exchange messages between aliens?

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not meet. Is it possible to transfer information between both species? What would be the mathematical precondition for information […]

RSA in plain English

I’m a computer science student, I’m not a mathematician, I don’t know anything about number or group theory. I’m looking at RSA, and I want to understand it. I know what Fermats’s little theorem and Euler’s totient function are, and this is what I’ve got: $p, q$ primes, $n=pq$. $d$ relatively prime to of $\varphi(n)=(p-1)(q-1)$. […]

Define ≡ in this situation?

“Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$.” (number $5$). I’m looking at this, and i’m not sure what the $\equiv$ means in this instance? I know the rest of the values, but what does $\equiv$ mean right now? Thanks in advance!