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

learn more… | top users | synonyms (2)

5
votes
2answers
215 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
1
vote
1answer
23 views

Question regarding Monoalphabetic Phi Test

I've been asked to prove the following system of inequalities; $$1 \ge \phi(T) \ge \frac{n-k}{k(n-1)}$$ Where $\phi(T) = \sum_{i=1}^{k} \frac{n_i (n_i -1)}{n(n-1)}$, $T =$ some text, $n = $ length ...
1
vote
0answers
32 views

statistical analysis of discrete (non-uniform) p-values: cryptographical random data test

i'm doing a statistical analysis of a well-known cryptographic algorithm and have hit an anomaly. i need to prove that what i have found is statistically significant. i am taking block sizes of 256 ...
0
votes
1answer
43 views

For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation ...
0
votes
1answer
53 views

Figuring out RSA Encryption from 1 encrypted and decrypted message

Suppose that you have an encrypted message and a decrypted message (just one). M (the public key) and k (the exponent you raise each number to) are public. Does having one copy both version of a ...
0
votes
0answers
38 views

DLP in a Cyclic group

Let q be a prime. G is a cyclic group of order $q^2$. Show that for solving the DLP in G it's enough to solve two distinct DLPs in two groups of order q . --- We are looking for an x such that ...
0
votes
1answer
25 views

Solving a congruence relation equation

I have the following equation: $$ n \equiv M^a\mod(b) $$ where n, a, b are integers, and M is unknow. How do i solve this equation to find the M value. Those a and b are public keys of the rsa ...
6
votes
0answers
50 views

A special case of zero-knowledge computation

This question is inspired by the disappearance of Malaysian Air 370. Let's suppose the plane crashed into the ocean. These are hotly contested waters where various countries (US, China, India, others) ...
1
vote
1answer
119 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
1
vote
2answers
71 views

Analyzing and decoding ciphertext

I have a worksheet which contains a dozen ciphertexts where the goal is to decrypt the encrypted English sentence(s). No information is given about what the text contains or what cipher methods are ...
1
vote
1answer
53 views

Does reducing 512-bit blocks to 128-bit hashes lead to 1/4 chance of collision?

This is a quote from a cryptography book called Implementing SSL / TLS Using Cryptography and PKI By Joshua Davies. MD5 operates on 512-bit(64 byte) blocks of input. Each block is reduced to a ...
1
vote
0answers
26 views

Single-Digit Errors

I've been assigned the following homework problem: Given an eight digit number $a_1a_2...a_8$ and a check digit $a_9$, $7a_1+3a_2+9a_3+7a_4+3a_5+9a_6+7a_7+3a_8+9a_9 \equiv 0 \mod{10}$ ...
0
votes
3answers
72 views

How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext?

I am currently attempting to learn RSA. Most of the literature I am using is at least a few years old, if not older. Given the advancements in computing and improvements in attacking RSA, I am wanting ...
0
votes
1answer
313 views

Finding points on an elliptic curve

I have an elliptic curve $$x^3+17x+5 \mod 59$$ $P = (4,14)$ is given and I need to find point $8P$. to calculate $8P$, I first calculated $2P$ by using the equation sigma = 3x^2+a/2y = ...
3
votes
1answer
88 views

How to find multiplicative orders of all elements in field $\Bbb F$ (say $\Bbb F_{13}$)?

I am working on some finite fields and I was referring to some online class material. Is there any way to find the multiplicative orders of all elements in a field $\Bbb F$?
4
votes
1answer
32 views

Part of verifying that the Weil pairing $e_m$ is well-defined.

As part of a homework problem, I need to show that the value of $e_m(P,Q)$ is independent of the choice of a point $S \in E[m] \setminus \{\mathcal{O},P,-Q,P-Q\}$, where $E[m]$ is the collection of ...
1
vote
0answers
52 views

determining the next random number pseudorandom number generator?

I have given 3 numbers let's say basic example x_0=5, x_1=6 and x_2=2 and modulus p is 7, ...
4
votes
2answers
69 views

Is it possible to do elliptic curve cryptography over $\mathbb{Q}$ instead of a finite field?

Whenever I read about elliptic curve cryptography (ECC), the writer always works over a finite field. But as I understand it there is no group-theoretic reason not to use $\mathbb{Q}$ as the ...
2
votes
1answer
86 views

E: $y^2+y=x^3$ an elliptic curve over $F_{2}$. How to prove the number of $E(F_{2^n})$ = $2^n+1$ if n is odd, …

Let E be the elliptic curve $y^2 + y = x^3$ over $F_2$. Prove $ $#E($F_{2^n})$$ = \left\{ \begin{array}{ll} 2^n+1 & \quad n=odd \\ 2^n+1-2(-2)^{n/2} & \quad ...
0
votes
0answers
29 views

Infinite One-Time Pad

As you know, when used correctly, a one-time pad allows one to send a message, such that the only thing that can be found out about it is the maximum size (which is also the key length.) It is ...
1
vote
3answers
88 views

Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom, attempt for ...
0
votes
2answers
337 views

Cube roots modulo $p$

Let $a$ be a positive integer. Is there any general method of solving equations of the form $$x^3\equiv a$$ modulo $p$, where $p$ is a prime number? Here are two examples: Example 1: In ...
1
vote
0answers
83 views

Rank of Quadratic Form

Let $n,m, s \in \mathbb{Z}$ be integers satisying $n=s^2$ and $m=2n$. Let $\newcommand{\bigmatrix}[1]{ \begin{pmatrix} #1_1 & #1_2 & \cdots & #1_s \\ #1_{s+1} & #1_{s+2} & \cdots ...
0
votes
2answers
117 views

decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
0
votes
1answer
39 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
3answers
65 views

Why does a key have to be at least as long as a message (cryptography)?

I am studying cryptography and find it hard to understand. What happens if the key is one bit or 100 bits shorter than the message?
1
vote
1answer
57 views

Can hash function be considered as linear functional?

I'm not very good in functional analysis or cryptography (so I'm not very sure in what I'm saying): A hash function (as I see it) is some kind of rule that makes an integer from an array (of letters ...
2
votes
1answer
238 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
25 views

Provide sample matrices that could be keys in the Hill cypher

Well, to encrypt some message I need to multiply parts of it by some matrix key, and to decypher it I need to multiply the output by the inverse matrix. But I've found an excercise to provide some ...
0
votes
2answers
130 views

Plaintext attacks: affine cipher

Consider an affine cipher with encryption function $e$, key $k=(k_1,k_2)$ and some prime $p$. The encryption function $e$ is defined as $e(m)=k_1m+k_2$ modulo $p$, where $m$ is some message ...
0
votes
2answers
56 views

Help me come up with a function

I have some numbers and corresponding numbers: 0 = 0 1 = 0 2 = 1 3 = 0 4 = 2 5 = 1 6 = 3 7 = 0 8 = 4 9 = 2 10 = 5 11 = 1 12 = 6 13 = 3 14 = 7 15 = 0 16 = 8 17 = 4 ...
1
vote
0answers
46 views

Closest vector problem

Given is a vector $v=\begin{pmatrix}2,&-1,&0,&1\end{pmatrix}$ as the shortest vector of the lattice $\Lambda (B)$, where $B$ is determined as $B=\begin{pmatrix}4 &-3 & 2 & 0\\ ...
1
vote
4answers
114 views

Using Euler Totient to compute digits in $3^{40000005}$

I'm trying to computer the two rightmost digits in $3^{40000005}$. Can this be done using the Euler Totient function alone as: For every digit $m >1$, $$m = \prod_{i = 1}^{n}p_i^{e_i}$$ where the ...
3
votes
1answer
43 views

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$? My doubt was specifically why, when raising to the power of the decryption key d we get a unique number ...
1
vote
1answer
146 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
0
votes
1answer
35 views

Periodic streams

I have problems proving the following result; Suppose you have two periodic streams $x_n$ with period $M$ and $y_n$ with period $N$. The streams $x_n+y_n$ and $x_n y_n$ are periodic with periods ...
0
votes
1answer
79 views

how to show a function is negligible

Let neg(x) be a negligible function. Let p be a polynomial function such that p(k)≥0 for all k>0. What can we say about f = neg(p(k))? Is f a negligible function? If yes, then is there ...
0
votes
0answers
38 views

enumerating in pseudo random order - version 2

edit 2: what kind of statistical test do I need to get an idea of the randomness of the order of a list? The list contains all base-4 numbers from 0000 to 3333 exactly once. edit 1: I've added ...
0
votes
1answer
86 views

enumerating in pseudo random order

edit 3: After more testing, I asked a new question with a jsfiddle enumerating in pseudo random order - version 2 edit 2: It's not a multiplication. It's more like a maze. A given column in row 1 ...
3
votes
0answers
203 views

Bachelor Thesis - Galois Theory Research Topics?

I'm on the last semester of my bachelor's degree (undergrad degree) and I will be writing my thesis next semester. I have talked to a professor at my university and one of the topics he suggested was ...
0
votes
0answers
59 views

Using knapsack problem for digital signatures

Is it possible to use the knapsack problem for digital signatures? What I am imagining is something like the Merkle–Hellman knapsack cryptosystem, but used for digital signing, rather than encryption. ...
1
vote
2answers
79 views

Determine a generator of $\mathbb{Z}^*_{11}$ manually.

What is the best/standard way to do this manually? Could you describe a solution in a step-by-step fashion.
2
votes
1answer
61 views

Determine the number of divisors in $K[x]$ of $1 + x^{15}$ and of $1+x^{120}$

where $K[x]$ is the set of all polynomials where coefficients are elements of $K$ $(0,1)$ Is this related to the problem of finding how many cyclic linear codes there are if $n = 15$ and $120$? I've ...
0
votes
1answer
106 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
2
votes
2answers
68 views

Manually performing the Miller-Rabin probabilistic primality test

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.
1
vote
1answer
73 views

Manipulating square roots mod p (prime) and when is $g^{ \frac{x}{2}} = p - z_1 \pmod p$ true?

tl;dr: If $z_1 = g^t \pmod p$ is one of the square roots of $g^x \pmod p$ such that $ \frac{p-1}{2} \leq t < p-1$. Then, does $p-z_1 = g^{\frac{x}{2}} \pmod p$ hold true? Say that we define a ...
0
votes
2answers
80 views

Explanation of $d^{-1}$ in modular arithmetic [duplicate]

I wasnt quite sure what to name this question, so that's what it is. I'me working on an encryption system, and I need modulus. I already asked a question on this, here, and I cannot figure out the ...
0
votes
2answers
59 views

How to make RSA function injective

I'm trying to make the RSA function $ F(c) = m^e \mod n $ injective (ie, always generates a unique value for $ c $ / don't repeat values in set $ C $). Through some research, I've found this is ...
2
votes
1answer
45 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
8
votes
2answers
457 views

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?

Why is does euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it ...