Latest Crypto related questions

I was thinking about the complexity of the Rabin-Miller primality test. On wikipedia I find O(k log3n), but there is no explanation. My idea was too simple. To see if n is prime, we have k attempts and with each attempt we check if first element b is 1, else we look for the -1 in the b-sequence. Here b = a^u mod n and n-1 = 2^l * u, u odd, with (b,b^2^1,b^2^2,b^2^3,...,b^2^(l-1)). So I assume worse-case ...

Basic question. I'm doing self-study on hash functions.

If I insert hello as input in a SHA512 hash function (e.g. using this) I get the following hash: 9b71d224bd62f3785d96d46ad3ea3d73319bfbc2890caadae2dff72519673ca72323c3d99ba5c11d7c7acc6e14b8c5da0c4663475c2e5c3adef46f73bcdec043

I noticed that the SHA512 algorithm yields the same output whether I input hello today or tomorrow, or if I use my computer o ...

G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well?

My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG which is a contradiction, since our initial assumption is that G is a PRG.

Does this proof make sense? Can anyone point out any mistake(s) made?

Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively.

Then, if I want to prove to someone that this computation have been computed properly without actually disclosing $x$, then I have to create a zero-knowledge proof of knowledge $\pi$ (which could be obtai ...

With an RSA key pair, from my understanding, Alice who holds the private key is able to encrypt a message into a signature. She would then send the signature together with her original message to Bob. Bob would then be able to use Alice's public key to decrypt the signature which would then return the message. The decrypted message would then be compared with the original message. If they are the same,  ...

Are both of these concepts related in someway. Can a group signature scheme be transformed into a multi-signature scheme?

A function G(x) = x || x (where “||” denotes string concatenation). It is given that G is not s pseudo random generator. Can someone describe how can we prove this. I am getting a bit confused in the concept of pseudo random generator.

What I have understood till now - The formal definition of pseudo random generator is given as $\Pr[PRG_{A,G(n)} = 1] ≤ 1/2 + negl(n)$. Here we can observe that  ...

I have just seen that there are 3 feistel based FPE schemes which were proposed FF1,FF2 and FF3( There might be many more). Although there have been different attacks on FF1 and FF3 standard that show that it does not preserve 128 bit security they are still used in practice with recommended changes.

What reason made FF2 fail completely and to be rejected from 2015 to be used any further?

I'm trying to learn about ECC. I understand that the points of the finite field are determined by taking the continuous elliptic curve and finding its points that have integer coordinates. Since ECC uses modular arithmetic, the points of the finite field are on an integer grid that extends from 0 to the modulus-1 in both x and y. The points of the field are determined by "wrapping" the continuous cur ...

Long story short, trying to understand how I would write the vigenere cipher mathematically when using Gen, Enc, Dec and I can't figure it out. This is what I've come up with so far.

$$\mathrm{Gen}: k ={0…25}^t$$

$$\mathrm{Enc}: c_i = (p_i + k_i) \pmod {26}$$

$$\mathrm{Dec}: p_i = (c_i – k_i) \pmod {26}$$

It doesn't really seem right though, so that's why I'm asking.

Is it possible to generate a private key from a public address and an extended private key?

For context: I am using C# and NBitcoin. The public address is generated from the outside via an extended public key and I have access to the mnemonic, extended private key, seed, etc.

I couldn't think of a better question to ask, but I will explain more here.

I want to be able to send a Word document to a server that will work with the document data. Are there any good ways to do that without the owner of the server to be able to read the content of the document him/herself? I only want a pre-made program on the server to be able to access the content. Eventually, when the pro ...

As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and calculate $-a^{2n}$ as $g$. First, what's this multiplication of $-1$ for? Second, why $a^{2n}$ not just $a^{n}$? I think $-1$ changes nothing and $a^{2n}$ will give us an element of order $\lambda/2$ more li ...

I have 12 bytes (5 fixed and 8 variable) of data that will be passed to SHA-256, at the end only the last 5 (most significant) bytes of the 20 generated are checked, is there a way to generate the 8 variable bytes to fake this type of SHA-256 check?

This paper says the CDH problem in a group of square matrices can be solved by a generalized Chinese remainder theorem. I wonder how this problem might be solved?

DH protocol in the cyclic group of matrices $\langle M \rangle$, and the matrix $M$ is considered as public information. It is assumed that Alice generates a random index $x$, calculates the matrix $M^x$, and sends it to Bob. In turn, Bob gener ...