How to better generate large primes: sieving and then random picking or random picking and then checking? I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q).

I know of two methods to achieve this, one based on a prime number sieve and another based on primality tests:

Use a prime sieve to find prime numbers within a random range, and then randomly pick a prime number from the output of the sieve.
Pick a number at random, and then test whether or not it is prime.

What is the best method, both from a security and efficiency perspective?

Both methods, of course, will work.

However, from an efficiency standpoint, (1) is considerably better.  Here's why:

The general strategy of both methods is to pick random numbers $R$, check to see that they have no small prime factors (smaller than a value $Q$), and then apply a rather expensive primality test (such as Miller-Rabin) to them.
The probability of a random number $R$ that we have already tested to have no prime factors smaller than $Q<R$ is about $log(Q)/log(R)$, and hence the number of expensive primality tests we expect to need is about $log(R)/log(Q)$.

Now, with method 2, after we pick a number $R_1$ at random, you will check to make sure it has no small factors smaller than some $Q$.  If it didn't, you'll run the expensive primality test on it, and if it wasn't prime, you'll go and pick another random number $R_2$ and try again, checking if that small number had no small factors.  The key point is that the effort you put into checking whether number $R_1$ had factors smaller than $Q$ cannot be reused when checking number $R_2$.  Therefore, we cannot make $Q$ that large (as we'll start spending a large amount of time just testing small factors).

On the other hand, with method 1, we set up a sieve that lists which numbers within the range have no factors smaller than some value $Q$, and then test those numbers that have no such factors.  Here, we pick the first number $R_1$ within the sieve, and run the expensive primality test on it, and if it wasn't prime, we'll go to the second number with no small factors in the sieve.  Here's the point: almost all the time taken in checking for small factors was taken setting up the sieve; once we've done that, going to the next number is essentially free.  That is, this method gets to reuse the effort in checking our test numbers for small factors.

Because of this, we can make the value $Q$ in method 1 considerably larger before it starts to become counterproductive; and because of this larger $Q$ value, fewer of the expensive tests are needed.

Now, as for security; method (2) has the obvious advantage that each prime of the correct size will be chosen with exactly equal probability, while with method (1), primes that sit over a long sequence of composites will be chosen with somewhat greater probability.  On the other hand, while (1) does choose primes with unequal probability, there's no know way that a factorization method can take advantage of that.  Because of this, method (1) is considered safe.


Case insensitive verification of HMAC / Base64 signature I am signing a short message using the base64 of an HMAC, like this (python):

import hashlib
import hmac
import base64

raw = hmac.new("key", msg="secret", digestmod=hashlib.sha1).digest()
base64.urlsafe_b64encode(raw)

That last line returns 'ux5F7Ye-rpwvysbzUBLu-wGaYXA=', which I use as the signature. To verify a signature we sign the data again, and compare with the user provided signature.

(The real implementation is Django's Cryptographic signing, the heart being salted_hmac. I'm simplifying a little for the question.)

How risky would it be to do the comparison case insensitive? e.g. the signature above would also allow 'ux5f7ye-rpwvysbzublu-wgayxa=' and many others.

Motivation is I am using the signature in an email address, which is case insensitive, which as you can imagine doesn't work. I can change to a different encoding (suggestions?), but that would require everyone updating the email addresses they use. I'm asking this question to see whether I can safely avoid making everyone do that.

Your worst case scenario is that all $18$ characters in the Base64 string are letters — this allows for $2^{18}$ possible collisions due to case-insensitivity. A normal SHA-1 hash is $160$ bits, and therefore has $2^{160}$ possible combinations. Divide by the number of collisions, and you have an effective strength of $142$ bits.

That said, I wouldn't necessarily recommend this. Far easier and less dubious would be to use Base32, which only uses uppercase letters.


Difference between mix networks and onion routing From what I know, the two seems to be the same:

Onion routing: Encryption is done in layers. Alice and server1 exchanges keys and she encrypts her message. Then, Alice and server2 exchanges keys and she encrypts again, creating layers of encryption. Alice then sends the whole layered encrypted message to Bob, and each server will only be decrypt a layer to reveal the address of the other server, which will finally lead to Bob.

Mix networks: Seems to be the same under the description and picture in Wiki, with just the nodes shuffling the order? Is mix network just a subset of onion routing?

What are the differences between the them?

A mix-net is a combination of proxy servers which bounce all the request into some sort of 'backpack' where anyone can see the whole thing going on but it would be really hard to tell which is which.
Example
We have Mike,Dom, Peter and Jean, they're using a mix-net and each one sends a request to the mix-net. what it'll do is that it'll take all the request, put them into a 'bag' and bounce them all and distributed each message to a new mix node, each of which also had a couple of messages in their bags already. Then those nodes distributed messages to 6 more mix nodes, and those mix nodes opened the messages and distributed them to recipients.

Difference Between a mix net and onion routing
using a mix-net someone could see your traffic but it might be impossible to determine where did it go due to the fact mix-net collects all the messages (http requests) and bounce them all.
another fact is that the mixing will just work if there's more than one message in the proxy server otherwise it will behave like onion-routing with a delay time.
mix-nets don't use encryption on layers as onion routing does.
Onion routing was developed to enable privacy not security thus someone could use a man in the middle between the first node and the last node of your circuit and using a traffic analysis it could find out. your location plus he'll know what you're looking for due to the last node will send the request to the destination without any encryption at all
Summary : if it wasn't because of all the messages,the bouncing and redirection a mix net would work as same as onion routing but without encryption.
For more info read: https://ritter.vg/blog-mix_and_onion_networks.html


RSA: How effective is this keypair-trash attack A question that could very well be part of xkcd's "what if?":

Let's say Monica made a piece of software that sends all RSA keypairs to a central database after they're not used anymore. Something like a keypair-trash. Let's say Monica has convinced everyone in the world to use this piece of software. Monica starts collecting keypairs on January 2015 and waits X years and collects all keypairs.

1) Given the current evolution of electronics and use of RSA, how many years would Monica have to wait so that a new keypair created has a 10% chance of being in the database? (you can apply certain limits like key length never changing)

2) If Monica had a DB that has 10% of all the possible RSA keypairs (within certain limits like length). Will the database be so big that searching a match is still too hard?

3) Would the attack be any more effective if Monica managed to put a keygenerating program in every consumer-grade device (with internet connection) of a country the size of the USA? The program uses all the devices spare time to generate keys and send them to her DB.

Without waiting to get a collision, there is a more annoying scenario : compute the gcd of all public keys you can scan over the net. Experience did show that a lot of systems do not generate enough unique entropy (Lenstra, A., et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, February 2012). Based on that scenario where everyone in a pool of 2000000 public keys use the same 4000 primes, the probability that 2 users get the very same combination of 2 primes is not so remote (the birthday paradox ....), and the response to your question is : yesterday, at latest. It did occur.

Let's assume that pseudoprimes from probabilistic testing do not interfere (they do, with a jackpot lottery probability!) ... when randomness is weak for integer generation, it is weaker for probabilistic tests.

Let's assume that you don't care about safe prime, strong primes, extra strong safe primes, and all the paranoid method of prime generation which might exclude all of them, because none is really strong and safe enough ....

Assuming your integer selection does not strictly follow some standards which only check the first prime candidate at the end of a prime gap, thus excluding all primes at the start of a prime gap.

Considering the evolution of software and electronics, Elliptic Curve is approximately 10 times faster at equivalent security levels and equivalent source code optimization levels. Monica's database will never fill.

Assuming Cloud Quantum Computing is approximately 60-70 years ahead and Wiki leaks  reveals in 30 years that NSA already has a 2048 quBit computer in a vault, this gives a end-of-life of 30 years to Monica database.

Assuming ....

Now, assuming that key generation is fair, everyone is using RSA2048 with 2 x 1Kbit primes and these prime numbers are evenly distributed in the range $[\sqrt{2} \cdot 2^{1023}, 2^{1024}]$, and are safe prime, i.e. $(p-1)/2$ is also prime. There are approximately c =

10474478420880630540417976938987964186481756527689107725320293990926166280934544
54955114259503095991159974600201604222625579123974838523076493430916373173064804
47871510202082442494709247560640274359031066510018408132368005212283030654515197
893087986785888352332881597122452139709939124879383308130303597

such 1 Kbit primes.

Assuming you like to play the national lottery and are familiar with a low probability $10^{-10}$ to see the first fateful collision event ( http://en.wikipedia.org/wiki/Birthday_problem ) and using a birthday paradox formula, then  $10^{-10} = 1 - \exp(-d^2/(2c))$.

You would need this number of keys:

$$d = \sqrt{ \ln(1.0000000001)\cdot 2c)}$$

d = 552129915947348069547969241673542619236474053
1711023498369601774599992268056593071378343449425
9320014789158954279395322381058948290665165722107332

At a rate of 1 new key per nanosecond, your key storage cloud solution must absorb 1 terabit of continuous throughput, plus the little 600% overhead of https connections, disconnections, you might require a computer the size of the universe (including the 99% of it which is supposed to exist amd has not been formally proved, and there will be no energy left to generate enough keys). But let's assume ....

The response is : you need

34195165591218423336373586540577052517638203484900091229
87420239096781423943440303949716847304675114278446095972
125316749920908117079065 years 92 days 3 h. 23 m. 10 s.

for a 0.000000001 % chance to witness a RSA key collision in your database.


Padding methods for block ciphers - PKCS7 vs ANSI X.923 I was looking through block cipher padding methods, and found two good candidates:

ANSI X.923 - pad with zeros, then a final byte for the padding length, e.g. 00 00 00 04.
PKCS7 - pad with bytes that each show the number of padding bytes, e.g. 04 04 04 04.

Is there any benefit to using PKCS7 over ANSI X.923 padding, or vice versa?

This site is a reference for padding:

http://www.di-mgt.com.au/cryptopad.html

Method 3 refers to the ANSI X.923 and method 1 refers to PKCS7.

The main advantage listed is that PKCS7 allows you to double check the number of padding bytes


AES + CBC encryption for a stream of UDP packets I am developing an application that is based on UDP, and I need to send a stream of packets. As you can imagine, packets can get lost or corrupted. I need to make sure that the content of those packets is encrypted, and I also need to be able to certify that the packet is correct when I receive it.

Finally, since performance is crucial in my application, I would like to keep the encryption overhead as small as possible. Often times, packets are relatively small, so even a few blocks can build up a relatively big overhead.

I don't have a reliable previous experience with cryptography, so I thought it was better not to trust myself on this.

Here is the strategy I have used until now (my application is far from being released, so having to change it more or less completely won't be so much of a problem).

First of all, packets are of fixed size, which is usually multiple of the block size of AES. I have no need whatsoever for padding, since messages aren't variable in length.
I use a shared key (obviously) and two fixed IVs, each endpoint uses one of the two to encrypt its messages. I use AES in CBC mode.
Since obviously using a fixed IV leads to a whole bunch of security flaws, I need to make my first block vary in a uniformly random fashion: that will act as IV for the next blocks.
Therefore, I prepend a block at the beginning of my packet. Its content goes as follows:

First four bytes: current timestamp in seconds
Next 12 bytes: zeros
I compute the sha256 hash of the message (32 bytes)
I xor the timestamp + zeros block with the first half of the hash
I xor the result with the second half of the hash

When I receive the packet on the other endpoint, I decrypt it with the key and the remote iv.
I compute the sha256 hash of the message (without the first block), xor the first half and the second half.
I xor the result of the hashing procedure with the first block.
If I get a timestamp that is no more than a few seconds ago, and 12 bytes of zeros, then the packet is correct.
If the packet is not correct, I just drop it, exactly as if I didn't receive it. No answer is sent back.

What are the flaws in this procedure?

At a high level, the major flaw is that you are rolling your own crypto protocol. You should strongly consider using a standardized protocol like DTLS.

Some specific problems:

Symmetric key distribution is left unspecified. Keys must be changed occasionally to thwart distinguishers.
No way to recover from symmetric key compromise.
Your message authentication code follows no existing standards and therefore is likely not secure.
If the attacker can get the IV, which is fixed, so likely not too hard, and can influence the first block of plaintext (which wouldn't be too hard since you are using timestamps), they can do some nasty things.
The fixed IVs add complexity that is unnecessary. For example, you have to trust the endpoints to not get the IVs mixed up.

There are probably a lot more issues that I haven't thought of in the short time I've been thinking about it. To solve this, use something standardized.


Is this algorithm good enough for small radio messages? This question is related to:

How to implement security - authenticity/confidentiality/integrity for 6/14 bits radio messages?

I am looking for a message that an attacker listening to the radio trafic will need at least 2 weeks to break it.

I came with this solution:

1 byte header
3 bytes UMAC
4 bytes Nonce (incremental number)
8 bytes data (encrypted with TEA)

Each party has its own keys for UMAC and TEA already known by the other party.

I would like to use the wiki umac implementation which has about 30 lines of C code and the wiki TEA implementation with 10 lines for encryption and the same for decryption. The small code is very helpful with my tiny microcontroller ram/flash size.

So, is it enough for my requirements? Can the message size be further decreased by implementing umac for unencrypted data and then encrypt umac+nonce+data altogether?

Edit - Clarifications on creating the message:

Compute TEA encryption for the 8 byte data with TEA key.

Compute UMAC with umac key and nonce for the previous encrypted data.

The keys don't change.

The question, even complemented with three useful comments, leaves me worried about the security of the system envisioned, for several reasons (from most to least serious)

The UMAC illustration in C code considered as reference in the question is secure only for single use of its key. Actual UMAC requires a block cipher, which is not stated in the question, and its code is sizably larger. While that block cipher could be TEA, that must not be TEA with the same key as the one used for encryption (that would at least invalidate the security argument of UMAC, and perhaps open to attacks).
It is not stated what the receiving device does when the UMAC check fails. If it allows other checks, including with another nounce, a 3-byte MAC seems hardly good enough: a forgery requires an average $2^{23}$ attempts (twice that if the nounce is forced to change), and at 100 per second that's less than a day. If on the other hand the receiving device stops operating when the UMAC check fails, there's a reliability problem. Rate-limiting is hard to make right, especially to make it resistant to Denial Of Service and/or random power loss.
A naive byte-per-byte implementation of the UMAC check could be very vulnerable to timing attack (reducing the average number of attempts to only about $3\cdot2^7$).
A less naive implementation doing the UMAC final check in constant time could still be vulnerable, because UMAC requires multiplication, and that's far from always constant time on a "tiny microcontroller".

Since the payload is so small (14 bits), there's a much simpler solution without UMAC (thus reducing code and removing 3 bytes in the message) that solves much of the above (in particular increases the expected number of attempts for forgery to almost $2^{49}$ attempts).

The idea is that

The sender enciphers with TEA and the fixed shared key a 64-bit block concatenating:

the 32-bit Nonce/incremental number
18 bits at zero
the 14-bit payload

The message (13 bytes rather than 16 in the question) is:

1 byte header
4 bytes Nonce (incremental number)
8 bytes cryptogram (Nonce, zeroes, payload encrypted with TEA)

The receiver(s) deciphers the cryptogram, checks that the deciphered 64-bit result starts with the Nonce (extracted from the message) and 18 bits at zero, and considers the message invalid otherwise. If a check of the Nonce is performed (e.g. that it is incremental), that check occurs only for valid messages.

This is demonstrably insensitive to timing attack as long as:

The implementation of TEA is constant-time (see note)
The 32-bit Nonce

is checked first and in constant time, e.g. using a single 32-bit compare,
or is checked together with the 18 bits at zero and in constant time.

Nothing with data-dependent timing is performed with the 14-bit deciphered payload when the above integrity check fails.
The TEA cipher is unbroken (as its stands).

Update per comment: the 32 bits of Nonce do count towards integrity. Argument: an adversary trying to make a forgery can either:

Reuse a 64-bit TEA cryptogram previously used in a genuine message, and then can either

Uses the Nonce in that genuine message; the message will pass the cryptographic check, but will be identical to the original message, thus does not count as forgery (beside, the repetition of the Nonce may allow rejecting the message, since the Nonce is supposed to be incremental)
Use a different Nonce; the message will be rejected, thus does not count as forgery.

Use a 64-bit TEA cryptogram that never was used in a former genuine message; assuming security of the TEA block cipher (and given that there can be as most $2^{32}$ genuine messages with a 32-bit the Nonce), the adversary has essentially no information about the result of the decryption of that block by the verifier. Whatever the value of the Nonce submitted to the verifier, the verifier will perform that TEA decryption, then a comparison including the Nonce bits, and the adversary has no way to predict the correct Nonce other than by trying (that's where at least the Nonce must be checked in constant time). Hence each additional bit of Nonce doubles the number of queries to the verifier (hence the duration of the attack) for a given forgery probability.

Update: if the header needs to be authenticated, change the 64-bit block format to 8-bit header, 32-bit Nonce, 10 bits at zero, 14-bit message; keep checking every bits except the message after decryption; and check at least header+Nonce (anything the adversary can vary) first and in constant time.

Note: In practice, it is hard to accidentally make TEA not resistant to timing attack. That would require the following two lines of code to exhibit a timing dependency w.r.t. v0 v1 k0 k1 k2 or k3, which is near impossible with 32-bit registers, and plausible only with smaller registers and code that does not use addition-with-carry or rotate-thru-carry.

    v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

(I often met C compilers for 8-bit CPUs that generate code with data-dependent timing for addition of a small constant to a variable, or addition of variables of different size; but never one that did that for addition of variables of the same size, as would  be the case here in practice).

Note: in practice, the hardest part is generating and checking the nounce robustly, in the presence of random power loss and/or DoS. Write and erase in EEPROM or Flash is not atomic, sometime fails, and occasionally leaves the memory cells in a state where the value read varies (with temperature, supply voltage, or random noise).


Output size of Salsa20 Salsa12 is in eStream portfolio. How many random bits one can generate in Salsa12 using single key? Is it $512\times 2^{128}$?

Salsa20 (and its variants) has 512 bit blocks, a 64-bit counter and a 64-bit nonce. So it can produce $2^{64}$ independent streams consisting of $512 \cdot 2^{64}$ bits each, for a total of $512 \cdot 2^{128}$ bits.


Is (1 bit HW signal) XOR (8 bits PRNG output) sufficient for a HWRNG? This is really a follow   up question   to a comment made regarding How to roll a HWRNG

In the situation of whitening a hardware generated random bit stream, "XORing the two bitstreams should be fine for mixing, by the piling-up lemma" was said.  The other bit stream was suggested to be one from a PRNG.

In signal sampling, it is rare to use the full range of ADC bits.  This is to avoid clipping the signal or saturating downstream amplification stages. Amplifier internal noise is typically related linearly to the input signal level, so more signal, more stray noise of the unintended variety. So for example in extremis, the hardware may only be sampling with a 1 bit width.

The PRNG will in all likelihood be outputting standard octets.

So the question arises, is

(1 bit HW signal) XOR (8 bits PRNG output)

sufficient to whiten a hardware random number generator, simultaneously ensuring that it's still a hardware generator rather than just a pseudo generator?

Side question:  would the PRNG have to be cryptographically secure or not? Consider that the system's numbers could still not be predicted with a simple RND() type generator due to the unpredictability of the hardware signal.

No, this is not a good way to whiten an HWRNG, and it definitely won't give you anything like true randomness.

It is true that the XOR of two independent bitstreams will, indeed, be at least as random as either of the original bitstreams.
However by XORing only one bit of hardware randomness into each byte of output, you're effectively padding each bit in the hardware RNG stream with 7 zero bits, making it very non-random even if the original unpadded hardware RNG was perfectly random.  You're also not doing anything to fix any possible biases in the hardware randomness except for XORing it with the pseudorandom bits.

In particular, this means that, if an attacker manages to discover the internal state of your PRNG (e.g. via statistical observation of the output, seven eighths of which is completely unaffected by the XOR), then they can trivially predict all but the lowest bit of each byte in the XORed output — and may even be able to guess the last bit with better-than-even probability, if the HWRNG output has less than 100% entropy.

(That last part would still apply even if you fixed your scheme to XOR each bit of the PRNG output with a separate HWRNG bit.  To actually achieve proper whitening, you really need to mix multiple HWRNG bits into each single output bit (preferably non-linearly), or at least feed them through a properly designed entropy pool.)


AES Diffusion at Block Level AES provides diffusion at the block level by implementing the ShiftRows and MixColumn sublayers. The former permutes data on a byte level, wheres the latter combines blocks of four bytes.

Can it ever be the case that this level of diffusion is insufficient?

That depends on how you define sufficient. AES achieves full diffusion after only two rounds, where diffusion is defined as the ability for every bit in the state to affect every other bit. That does not mean that a mere two rounds can protect against cryptanalysis. The number of rounds necessary to avoid fatal cryptanalysis is something that can only be chosen by studying the cipher and attempting to break it. During the AES standardization process, the cipher Rijndael, which became AES, was given 10 rounds for the 128-bit key size because the best attack against it could break 6 rounds. The extra rounds were considered to be a safety net, or security margin, against future advances in cryptographic attacks.

Is this always going to be sufficient? We don't know. Right now, no attack more efficient than exhaustive search is known that can break every round in the cipher in order to violate its security properties. Some have argued that 10 rounds is not enough, and even suggested that it be raised to 18 or 24 during the AES process, but that never happened and it was standardized as 10, 12, and 14 rounds for each key size. However, as the years have passed, we still do not have any cryptanalysis that breaks every round.


Streaming hash function OK, so we've had questions about hashes build from stream ciphers (not a good idea) and about stream ciphers made out of hashes (yes, of course, use counter mode). What I want to ask is related but doesn't seem to have been asked before.

Is it possible to make a streaming hash? With a "streaming hash" I mean a hash function whose state is updated for each separate byte, instead of the byte itself having to be cached until a full message block is known.

Or, to turn the question around, is it required to always split the message into blocks instead of processing bytes? Or is this just an artifact of the functions used internally by the hash?

As CodesInChaos mentioned in the comments, you could simply set the size of the digested block to one byte (or bit, if that is your preference). Also as mentioned in the comments, this will not necessarily work nicely with any given hashing construction.

Is it required to always split the message into blocks instead of processing bytes?

I am not sure how you would process any input without breaking it into some kind of blocks. Considering that a block can be an arbitrary size that is usually defined by the algorithm in question, a block could range from 1 bit to however many bits constitute a complete input message. One bit is a valid blocksize, one byte is a valid blocksize, and X-Y bit words for any X and Y is a valid blocksize.

So I would say yes, it is unavoidable to split the message up into blocks for processing. Input of any length that you feed into the compression function constitutes a block. This seems unavoidable, unless you simply don't compress any input. Even if you compress the entire message at once, you are still working on one block.

Is this just an artifact of the functions used internally by the hash

The blocksize influences the performance of the compression function. If you digest 512 bits at a time using X instructions, clearly this will digest data much more quickly then digesting 1 bit at a time using the same X instructions. This assumes the CPU has appropriately sized registers and instructions for operating on the desired word size - which may not necessarily be the case.


A fair peer-based coin-flipping protocol? I found this question on the game programming site and was intrigued.  I came up with an answer off the top of my head but I'm no cryptanalyst so it is probably not water-tight.
This is how my idea goes:

each of the two peers generates a random number.

each peer creates a salted hash of its number and sends it to the other peer.

once both peers confirm reception of each other's hashes, each then sends the other its actual random number.

each peer verifies that the hash sent by the other is actually a hash of the random number.

the result of the coin flip is the XOR of the least significant bit of each number, i.e.
(a & 1) ^ (b & 1)

So would it work? If not, how could it be made secure? Is there some conventional method for solving problems like this one?
The rules are, there are two untrusted parties with no intermediary.  Assume the channel of communication is secure.  Neither party must be able to unfairly win or lose.

Yes, your basic idea is feasible.  What you are describing is a distributed coin flip protocol based on a commitment scheme.

However, you protocol as described is vulnerable to replay attacks: after one peer receives the other's hash, they can send back the same hash, wait for the other peer to reveal their random bit and salt, and send back those as well.  That way, they can force the outcome of the XOR operation to always be 0.

There are a number of ways to modify this protocol so that this attack won't work:

include a unique peer ID in the hash input,
abort (or restart) the protocol if two peers produce the same hash value, or
require the peer who revealed their hash last to be the first one to reveal their inputs.

Any one of these modifications would be enough to prevent this attack.

Edit: I thought this seemed familiar.  Here's my earlier answer to essentially the same question.


Zero knowledge proof of dependency Is there any ZK protocol that can be used to prove dependence of two entities. More specifically, if there are x(dependent) and y(independent), is there protocol to prove that x is dependent or function of y, without revealing the function it self.

  Edit: As replies below suggested, I thought to provide concrete form of dependent function. So for example x= 2+y another example can be x=ky, where k is yet another independent variable. In short, x can be even more complicated function of y.

Any NP statement can be proven in zero knowledge (not necessarily practically efficiently, but yes in polynomial time). So, if you can define what you want as an NP relation then it can be done. However, in order to do that, you must define what you mean by "dependent" and so on.

Such statements can also be highly efficient. For example, it is possible to efficiently prove that a tuple of elements if of the "Diffie Hellman type". Informally, one can prove that for some $(g,h,u,v)$ there exists a value $r$ such that $u=g^r$ and $v=h^r$ (where $g$ is the group generator and all operations are in the group). Observe that this is exactly a proof that $u$ and $v$ are ''dependent'' variables.


Changing SRP-6a message order In SRP-6a, the public key $B$ of the server is normally sent after receiving the public key of the client $A$. Is it okay to send $B$ and $s$ after the client sends its username $I$, but before the client sends $A$?

Yes, it's okay.

This is actually mentioned in passing in the SRP 6 design paper. Previous versions used a random $u$ where an attacker who saw (or could predict) it before revealing $A$ could compute $A = g^a v^{-u}$ and use this to effectively cancel out the long term secret. With $u$ derived from a hash, even if the attacker saw $B$, the dependence of $u$ on $A$ means that they would need to break the hash function to be able to find a suitable $a$/$A$ for an attack.


What does the symbol $W_t$ mean in the SHA-256 specification? I'm really confused about the computation about SHA 256.

$$W_t = \begin{cases}
M_t^{(i)} & 0 \leq t \leq 15 \\
&\\
\sigma_1^{256}(W_{t-2}) + W_{t-7} + \sigma_0^{256}(W_{t-15}) + W_{t-16} & 16 \leq t \leq 63
\end{cases}$$

The $W_t$ variable: What's the value of $W_t$? How do I get that value?

I'm still confused because of the explanation using the English language. I'm a beginner guys, any help from you will be a plus point for me about hashing.

It is in SHA-256 message schedule (NIST-FIPS 180-4);

The message $M$ with length $l$ is first padded as the usual way;

append 1 to the end of the message,
then, add $k$ zero bits such that $$l+1+k \equiv 448 \mod 512$$
finally, add the length of the message in 64-bit. Now, the total padded length is divisible by 512.

After padding, the padded message parsed into $M^{1},\ldots,M^{N}$ where each has size 512-bit.

The sub index $t$ represents 32-bits in 512 bits. Thus, The $M_t^{(i)}$ is the $t$-th 32-bit in the $M^{(i)}$ for $0 \leq t \leq 15$

The $W_t$ is defined as your equation;

$$W_t = \begin{cases}
M_t^{(i)} & 0 \leq t \leq 15 \\
&\\
\sigma_1^{256}(W_{t-2}) + W_{t-7} + \sigma_0^{256}(W_{t-15}) + W_{t-16} & 16 \leq t \leq 63
\end{cases}$$

Where
$$\sigma_1^{256}(x) = \operatorname{ROTR}^{17}(x) \oplus  \operatorname{ROTR}^{19}(x) \oplus  \operatorname{SHR^{10}(x)}$$
$$\sigma_0^{256}(x) = \operatorname{ROTR}^{7}(x) \oplus  \operatorname{ROTR}^{18}(x) \oplus  \operatorname{SHR^{3}(x)}$$

$\sigma_1^{256}(x)$ and $\sigma_0^{256}(x)$ operate on 32 bits and produce 32 bits.

Note: the 256 above the $\sigma$ represents the 256 in SHA-256. Similarly, there is $\sigma_0^{512}(x)$ and $\sigma_1^{512}(x)$ for SHA-512.


What is wrong with AES-CTR-HMAC-SHA256 - or why is it not in TLS? It seems the only specified CTR mode ciphers in TLS are all GCM based.

GCM ciphers run AES-CTR and do authenticated encryption with a MAC based on Galois-field arithmetic ("GHASH") - and the latter seems to be difficult to get right in software (side-channel attacks, constant time) or require CPU hardware support (e.g. Intel AES-NI / PCLMULQDQ) which in turn might be manipulated/weakened via microcode updates/implants.

On the other hand HMAC-SHA256 seems relatively simple to do right in software and when used together with AES-CTR and a encrypt-then-MAC scheme.

So why are there no modes like TLS_DHE_RSA_AES128_SHA256?

The closest I could find is this unfinished, expired IETF draft.

Short answer:

There would be nothing (that isn't already wrong with TLS) necessarily wrong with a CTR + HMAC cipher suite, but the technical merits are only one factor in a technical feature getting to RFC status in the TLS working group.

Without being discourteous to the TLS Working Group (WG) participants or process, other reasons can be: political (including national/standards body alignment); personal/corporate preference/motivation; historical timing; resistance to change (modifying implementations is an often-cited cost); fear/uncertainty/doubt/apathy/debating skills etc.
TLS standardization happens very much in a real world implementation + real humans interacting environment, where the isolated technical merits of an idea are by no means the only measure of, or contributing factor to, success.

Why the draft-ietf-tls-ctr in particular never made it to RFC status (as part of TLS 1.2 or separately) is a little murkier, but my best guess is that a combination of:

timing and politics: probably most importantly, AEAD modes such as GCM, many based on CTR mode, and in the case of GCM favoured by a NIST standardisation process, came along early in the TLS 1.2 process and probably supplanted CTR in the thinking of the WG editors/participants.
uncertainty: CTR in 2006 was relatively less known and trusted compared to CBC.
doubt: there were some concerns stated in the TLS WG discussions about its use in DTLS and with explicit vs implicit IVs
Eric Rescorla was both an author for draft-ietf-tls-ctr and co-editor of the TLS 1.2 draft, so I suspect once GCM became a preference for the WG he stopped editing and pushing the CTR mode.

Longer timeline:

Nov 2005

First mentions of draft-ietf-tls-ctr at Oct 2005 TLS WG meeting, at this stage not a chartered WG item.
Feb 2006

draft-ietf-tls-ctr 00 begins life as a companion draft to the TLS 1.2 draft 00.
March 2006

draft-ietf-tls-ctr is listed on the March 2006 TLS WG meeting agenda
The TLS WG charter at that time explicitly discusses counter mode cipher suites as being a goal of TLS 1.2.

The March 2006 TLS WG meeting minutes refer to draft-ietf-tls-ctr as being a chartered item and ready for review.

At this point the First draft of TLS 1.2 specification, including CTR mode cipher suites milestone is marked as Done but CTR modes are clearly not in draft 1.2 specification at that time (or any other).
July 2006

At the July 2006 TLS WG meeting draft-ietf-tls-ctr is described as ready for last call in the minutes.

No last call for draft-ietf-tls-ctr eventuates on the TLS WG mailing list.
October 2006

TLS 1.2 draft 02 is published, and AEAD/GCM modes are included for the first time.
November 2006

At the Nov 2006 TLS WG meeting draft-ietf-tls-ctr is still on the agenda, and the minutes show discussion centered around the counter and IV structure.  A GCM mode draft is mentioned as being imminent.
December 2006

Some concerns about counter mode, in particular counter/IV structures, are discussed on TLS WG mailing list.
January 2007

Discussion of CTR mode on the TLS WG mailing list has dried up apart from some discussion about potential issues with DTLS, and GCM mode is being actively discussed.
March 2007

draft-ietf-tls-ctr is still mentioned in the TLS 1.2 charter, but no longer on the March 2007 TLS WG meeting agenda, and all discussion in the minutes is about GCM.

From this point on draft-ietf-tls-ctr is not mentioned again, and no CTR modes end up in TLS 1.2. GCM modes go on to be published in RFC 5288 about the same time as TLS 1.2 is finalised in RFC 5246.


How to recover secret $x$ from Elgamal signatures with repeated $k$? Set generator $g \equiv 5 \pmod p$ where $p=647$ and $p$ is prime.

With the same $g$, $p$ and secret signing key $x$, Alice sends two messages, $428$ and $129$, with signatures $(433, 239)$ and $(433, 100)$ respectively. She uses the same ephemeral key twice.

The question says without using a discrete logarithm algorithm, determine
both her secret signing key $x$ and her ephemeral key $k$.

Could anybody help me in what direction I need to go to solve this?  I'm not sure what to do without the use of discrete logs.

Given two ElGamal signatures $(r_1, s_1), (r_2, s_2)$ that used the same $k$ when signing will have the same $r$ value since $r \equiv g^k \pmod{p}$ and $g, k, p$ are all fixed. Now, given that $s \equiv (H(m) - xr)k^{-1} \pmod{p-1}$ we observe the following:

$$s_1 - s_2 = ((H(m_1) - xr_1) - (H(m_2) - xr_2))k^{-1} \pmod{p-1}$$

But $r_1$ = $r_2$ so we can reduce this futher:

$$s_1 - s_2 = (H(m_1) - H(m_2))k^{-1} \pmod{p-1}$$
$$k = (H(m_1) - H(m_2)) * (s_1 - s_2)^{-1} \pmod{p-1}$$

Once we have $k$ we can use it to recover $x$ by rewriting the formula with which $s$ was initially computed:

$$x = (-r^{-1})(sk - H(m)) \pmod{p-1}$$

We know $r, s, k, H(m)$ so we just plug them in and solve for $x$.


What does this step in this protocol for the Yao's Millionaire Problem mean? I was reading “An Efficient Protocol for Yao’s Millionaires’ Problem” (Ioannidis and Grama 2003). In the proposed protocol in section three, it is written:

  (Step 4) For every $i$, $1 \le i \le d$, Bob obliviously transfers $A^\prime_{il}$ where $l = b_i + 1$.

(Some context: $d$ is a security parameter, $A^{\prime}$ is a matrix of size $d \times 2$, and $b_i$ are the bits of Bob's number.)

I understand the definition of 1-2 oblivious transfer, however, I am confused exactly what Bob is obliviously transferring.  Is it referring to the bits of $A^\prime_{il}$? If so, the paper explicitly says that only 1-2 transfers are used, so does that mean that $A^\prime_{il}$ is no larger than $2$ bits?

In here, it is 1-2 oblivious transfer meaning that for each $i$, the receiver gets $A'_{i1}$ or $A'_{i2}$ but the sender does not know which. The length of the elements $A'_{ij}$ is not important as long as you choose a correct oblivious transfer protocol.


Encrypt or decrypt using the private key, and decrypt using the public key? I am currently trying to figure out if my following scheme is implementable in ECC or whether I can use existing implementation. At first I was going with libsodium but it seems that it really doesn't support my use case.

My scenario: There are basically two groups. Group A which has read access (only decryption) and Group B which has write/read access (both encryption/decryption).

libSodium has something which is very similar: crypto_box_seal/crypto_box_seal_open

The issue with libSodium's api is that crypto_box_seal_open requires both keypairs. I would need the reverse of this api.

eg.

private key => encryption/decryption
public key => decryption

Does a scheme like this exist?

What you want is called a signature scheme. This will enforce the separation concerning the right to write. If you need confidentiality as well, you can combine this with traditional symmetric or public-key encryption.

So how does this work with signatures? Whenever somebody from Group B writes the data, they remove the old signature and apply a new one. Now anybody from Group A or B can verify that the file has not been modified since it was last edited (by a member of group B). Of course, members from group A won't be able to sign the file, because their public signature keys won't be added to the central list of trusted signature keys. Alternatively one could also use something called a ring signature which also guarantees anonymity of the original writer (or a group signature if attributation is wanted).


Public Key Encryption for Message Confidentiality In public-key encryption, if the decryption algorithm is
$$\text{Dec}(k_i,\text{Enc}(K_i,p))=p$$
where $k_i$ = receiver's private key and $K_i$ = receiver's public key
what would be the algorithm for encryption? Would it be
$$\text{Enc}(K_i,\text{Dec}(k_i,c))=c$$
Just looking for some clarification.

The question's formula $\text{Dec}(k_i,\text{Enc}(K_i,p))=p$ is for both encryption and decryption.
Encryption is $p\mapsto\text{Enc}(K_i,p)=c$.
Decryption is $c\mapsto\text{Dec}(k_i,c)=p$.
Note that $\text{Dec}$ can be a true function, but $\text{Enc}$ likely has a hidden random argument. Otherwise encryption would be deterministic, and deterministic encryption is vulnerable to chosen-message attack, especially public key encryption. If a name on the public class roll is encrypted with deterministic public-key encryption (such as textbook RSA encryption), anyone can find the name from the ciphertext, simply by enciphering all names on the class roll and comparing with the ciphertext.

In a textbook RSA context, $\text{Enc}(K_i,\text{Dec}(k_i,c))=c$ would be equivalent to textbook RSA signature of message $c$ followed by textbook RSA signature verification. But it is using a confusing notation, that won't work in most other signature contexts (e.g. Schnorr signature, DSA, ECDSA, EdDSA).


How does the wider cryptographic community view non-abelian group based cryptography? Is there perhaps some neural expository article on crypto systems based on non-abelian groups?

I've gleaned that Anshel–Anshel–Goldfeld key exchange is the most well-known cryptographic algorithm based upon non-abelian groups.  Do people consider it respectably secure?  Why?  Why not?

Any opinions about the role of combinatorial group theory here?

I'm curious because, as I understand it, non-abelian finite groups aren't considered particularly useful in cryptography, due to the Coincident Group Orders Theorem that follows from the Classification of the Finite Simple Groups, but obviously infinite non-abelian groups are another matter.

Almost all cryptographic algorithms which use groups actually work in subgroups generated by a conventional element; even if the group as a whole is non-abelian, the subgroup is cyclic, thus abelian. The Anshel-Anshel-Goldfeld protocol tries to use non-commutativity itself, and relies on "how much non-abelian" the group is.

All asymmetric cryptographic algorithms rely at some point on a presumably hard problem. We do not know whether hard problems really exist, neither asymptotically (that's the whole P=NP problem) nor in practice (when given a specific computational budget, e.g. $2^{80}$ elementary operations). Our only tool is accumulation of work: we take many cryptographers and mathematicians, we let them loose on the problem for a few decades, and we see if they find some way to solve the problem.

To be honest, I had never heard of the Anshel-Anshel-Goldfeld protocol before this morning. It is described in an article which was published in Mathematical Research Letters, which is not usually associated with cryptologic research. There is a bit of research on doing cryptography with braid groups (the AAG protocol is just an instance of that); see this page for a lot of relevant pointers. It is still a recent and widely unexplored area, so, regardless of its inherent merits, the AAG protocol cannot be deemed secure yet. Also, it is only a framework, explained generically over an unspecified non-abelian group; it cannot be declared secure in abstracto.

Infinite non-abelian groups, or anything infinite for that matter, have a slight practical issue: they do not fit well in actual computers which have only a finite amount of RAM. Even for infinite sets where each element can be encoded in a finite (but unbounded) amount of RAM, such as plain integers, variable size easily leads to side-channel leakage, and that's a bad thing.


Hash functions vs. keyed hash functions in the context of private key generation I'm designing a key distribution mechanism and have thought of using a securely generated/acquired private key as a seed for a sequence of private keys to be distributed to a number of users using a key encryption key which is exchanged through a secure channel during the initialization step.

The setting is as follows:

k is a secure private key
h is a cryptographically secure one-way function

n keys are generated using h and k:

$$
k_1 = h(k)
$$
$$
k_2 = h(k_1) = h(h(k))
$$
...
$$
k_i = h(k_{i-1})
$$
...
$$
k_n = h(k_{n-1})
$$

This scheme broadens the surface of attack as if one key is compromised, all subsequent key can be easily compromised as well.

Would it be more secure to use a keyed hash function to generate the keys, using a hash of the original key as the input key for the respective hash function?

There's actually an algorithm designed exactly for this purpose: generating a sequence of keys from one master key.  It's called HKDF (HMAC-based Key Derivation Function, paper here).

The algorithm essentially boils down to two steps: Extract and Expand.  The Extract step accepts any type of "key material" as input, and outputs a pseudorandom key that will be used in the next step.  The purpose of this step is to eliminate any patterns, structure, or bias in the input key, and produce a uniformly pseudorandom output.

If the master key is already a string of uniformly pseudorandom bytes (i.e. it was generated using a crypto-secure RNG), it's safe to skip the Extract step (but be sure to read the notes in the RFC).

The second step, Expand, uses the pseudorandom key from the first step to produce an arbitrary length output.  Typically, Expand is used to produce a long output, and that output is divided up into smaller keys (e.g. 1024 bits divided into four 256-bit keys).  However, it is also possible to use Expand once for each key, while providing a different value each time for the "info" parameter.  This is likely slower, but may be more elegant from an engineering perspective.

HKDF is carefully designed to avoid the problem you identified.  If any of the output keys are ever revealed to an attacker, the remaining keys are still safe.  Of course, if the master key is discovered, game over.

I suggest reviewing the RFC: it's reasonably straightforward, and includes many helpful suggestions on usage.  Section 2 has a precise description of the algorithm.

With regard to performance, let's assume you skip the Extract step and use HKDF with a hash function whose output size matches the desired key size.  The algorithm can now be simplified to $\operatorname{HMAC}(\mathit{key}, \mathit{info} \| 1)$ (where $1$ is the single byte 0x01).  If performance is important, it's possible to precompute parts of the HMAC calculation given the master key.  Assuming a short "info" parameter, only two invocations of the underlying compression function are needed per key (assuming the use of a Merkle-Damgard hash function like SHA-2, SHA-1, or MD5).

Contrast this with a scheme such as $h(\mathit{key}, \mathit{info})$ (a keyed hash function).  With optimizations, only one invocation of the compression function is needed per key.  However, this gives up (1) the security analysis and arguments provided by HKDF, (2) HMAC's additional security against breaks in the hash function, and (3) forces you to consider length extension attacks, among other things.


Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security properties, hence the need for post quantum crypto algorithms.

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

This is relevant because SEC2 defines a bunch of elliptic curves over $F_{2^m}$ instead of $F_P$.

I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

Quite applicable; Shor's algorithm treats the group operation as a blackbox, hence it treats an even characteristic curve just like it does a prime curve.
  The only practical difference is the cost differential (in terms of qubits, circuit complexity and depth) between the prime curve and the even characteristic curve addition operations.

  I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.

That's a different question (because GCM/GHASH has a secret symmetric key); in terms of standard CPA and CCA attacks, GCM/GHASH (correctly used) is provably secure as long as you cannot distinguish AES (or whatever underlying block cipher you're using) from a random permutation; allowing the adversary to perform Quantum operations doesn't change that (and so unless he can use his Quantum Computer to break AES, there's nothing he can do).

The one exception is if you go outside that model, and go to a Quantum Oracle model (where the attacker is allowed to request entangled queries and get entangled responses), that's different - it's known that GHASH (that is, the authentication piece in GCM) can be broken fairly easily.  This does show that it is impossible for a white box GCM implementation to be quantum secure; however it is hard to come up with another realistic scenario where this attack is applicable.


Secret Sharing Scheme with variable share size? Is there a secret sharing scheme construction that allows the shares to have different sizes/lengths?

For example a (3,3) scheme, where shares 1 and 2 have large sizes while share 3 has a very small size.

Adapt Shamir's scheme using a high degree, say degree $d$ polynomial.

Thus $d+1$ shares result. Share them out to 3 users, say giving $d/2$ shares to User 1, $d/2$ shares to User 2, and 1 share to User 3.

Edit: As noted by @Ilmari Karonen this doesn't allow you to make shares shorter due to information theoretic reasons explained in his answer.


Signing the hash of a key with the same key Given a private signature key sk and a public signature key SK, does revealing sk(H(SK)) (in addition to SK) make it more easy for an attacker to determine sk or to fake a signature that would appear to have been produced by sk? Is this scheme a bad idea - in other words, does it compromise the secuity of the signing algorithm? (It seems like this is analogous to key-dependent encryption, but for signatures, and with the interposition of a hash function in between).

If that matters, I'm using ECDSA signatures. Any pointers are appreciated.

No, signing the hash of the public key cannot introduce a weakness on a secure signature scheme.

When we have a signature scheme, we assume that it is secure in an chosen text model, where the attacker has access to the public key, and can ask any text of his choosing to be signed.  We can see that any such scheme (such as ECCDSA, or so we believe) cannot be specifically weak this way.

This is easy to see; suppose we had a weakness that was caused by this (whether it revealed the private key, or made it easier the create a forgery).   What the attacker could do is hash the public key, and then ask that hash to be signed.  If the public key system had a weakness, this signature would reveal it, hence showing that the signature scheme didn't meet the requirements of security in the first place.


Is rekeying attack the same as related-key attack? I've been searching about rekeying attack, but what I found is always using the term "rekeying/related-key attack". Is rekeying attack the same as related-key attack?

No, rekeying is about changing keys: https://en.m.wikipedia.org/wiki/Rekeying_(cryptography)
And we can have attacks ob the process of changing the key without need to have related keys. Which are two(or more) keys with some relation to each other which may lead to an attack.


Initialization vector length insufficient in AES I use AES with AES/CBC/PKCS5Padding with the following encryption and decryption code sections in Java:

cipher.init(Cipher.ENCRYPT_MODE, keySpec, new IvParameterSpec(IV1));
cipher.init(Cipher.DECRYPT_MODE, keySpec, new IvParameterSpec(IV2));

where IV1 and IV2 are randomly generated 16-byte initialization vectors. As you can see, the initialization vectors in encryption and decryption processes are different. This leads the bytes of the decrypted message to be right after the first 16 bytes such as the message:

Enter your message here...

becomes

*****************ge here...

after enc/dec where * denotes a wrongly decrypted byte as it should be as IV1 and IV2 are different.

My question is: What to do to encrypt and decrypt text with length greater than 16 bytes using AES with initialization vector?

CBC mode is a method of encrypting messages of arbitrary length; it can handle messages longer than 16 bytes, and it takes an fixed length IV (16 bytes in the case of AES) for each message.  So, if the question is "how does CBC work for messages longer than 16 bytes (even if the IV is only 16 bytes)", the obvious answer is "quite well, thank you".

The source of your question would appear to be "in the case I tried, the decryptor used a different IV than the encryptor; how could it decrypt properly after the first 16 bytes?"  The answer to that is, well, that's how CBC mode works.  On an IV mismatch, the first 16 bytes will be garbled, and the rest of the message will decrypt properly.  Actually, this isn't limited to only the IV; the ciphertext has a similar property; if you modify bytes 0-15 of the ciphertext, then bytes 0-15 and bytes 16-31 of the decrypted plaintext will change, but the rest of the decryption will be unaffected.  This happens because block N of decrypted plaintext is a function of blocks N and N-1 of the ciphertext (and no other part of the ciphertext); if N=0 (the very first block), the IV stands in for block -1 of the ciphertext.

Also, you are probably already aware of this, but I'll add it anyways: for CBC mode to work, both the encryptor and the decryptor need to use the same IV for a message.  Now, the most common method of achieving this is to have the encryptor select the IV randomly, and send the IV it used along with the encrypted message.  This works (and it's easy to show that giving the IV to an attacker doesn't help him), however, that's not the only possible method; both sides could be able to select IVs via a formula.  It turns out it is important that someone in the middle can't predict the IV's that we'll use before the message is sent (otherwise there are subtle attacks); but as long as we have that, deterministic IV generation is possible.

And, if you're looking at your experiments and are wondering "if the decryptor can decrypt after the first 16 bytes, why doesn't the encryptor just add a dummy 16 bytes, which the decryptor ignores", well, the surprising answer is that it works well.  In fact, that turns out to be equivalent to selecting a random IV, and sending it along with the message (in the 16 bytes immediately prior to the ciphertext).

My guess is that you're not really interested in digging into how CBC and AES work internally, and so I won't go into those details. If I am wrong, you can get started by looking at Description of CBC Mode; if you have further questions about that, well, this is a good forum for asking those questions.


q-Strong Bilinear Diffie-Hellman I'm having trouble finding the first paper that introduced the $q$-Strong Bilinear Diffie-Hellman ($q$-SBDH) assumption which, roughly speaking, is:

Let $\mathbb{G},\mathbb{G}_T$ be two groups of order $p$, with a bilinear map $e$ from $\mathbb{G}$ to $\mathbb{G}_T$.
Let $s \stackrel{$}{\leftarrow} \mathbb{Z}^*_p$ be a trapdoor. Given $pp = \langle g, g^s, g^{s^2},..., g^{s^q} \rangle \in  \mathbb{G}^{q+1}$, an adversary has negligible probability of finding $\langle c, e(g, g)^{\frac{1}{s+c}} \rangle$ for some $c \in \mathbb{Z_p} \setminus \{-s\}$.

Some papers seem to point to Dan Boneh's "Short signatures without random oracles and the SDH assumption in bilinear groups" (Journal of Cryptography, 2008). However, as far as I've read the paper, only $q$-SDH is defined there, not $q$-SBDH.

Any help would be appreciated!

After some more investigation, the earliest paper I could find that introduces $q$-Strong Bilinear Diffie-Hellman was Reducing Trust in the PKG in Identity Based Cryptosystems by Vipul Goyal in CRYPTO 2007.


Designing a protocol to record attendance to lectures Scenario: a class that is not mandatory. The teacher wants a protocol that will satisfy the following requirements:

It must record each student's attendance.
A student X should not be able to say that another student Y went to the lecture.
The teacher should not be able to know who attended the lessons and who didn't until the end of the term.
It must provide integrity and non-repudiation.
It must be simple and fast.

This is what I thought:

Suppose that there are N students enroled.

Each class:

The teacher generates N random numbers, stores them somewhere safe, and writes them down on a separate piece of paper.
He gives one of these to each of the students that attend a class. He asks them to sign the reverse of the paper.
The students sign, and give the piece of paper to the teacher.
The teacher can check whether a student invented a number.

At the end of the semester:

The teacher asks for ID of each of the enroled students (or any other document that contains the signature), so he can now know who attended each class and who didn't.

Are there any visible flaws?

Facing the same problem in an undergraduate class of about seventy students, I know of someone who came up with the following simple and effective solution because signing a paper had proven to be an undependable method for recording attendance:

In front of one of the four assistant instructors, he had the students present their IDs at the front desk as they came in, and an AI actually checked the photo of each student prior to scanning.  Students were not allowed to scan themselves in, and he used an OpenOffice Calc spreadsheet to record their data. This made things reliable--the bar code reader populated the spreadsheet in front of an AI.  It also made it easy to record lateness.  Names were not recorded, only ID numbers, which the AIs did not know. He did not know anyone's ID number off the top of his head, but he could find out all of them.

For this to work in the way you wish, you would need to map each ID number to a new, class-specific number, and only let the certain people in the administration have access to a student's real ID number.

Or you could make an attendance card for each student in your class with a photo and bar code/ QR code, and use a good pseudo-random number generator to create their temporary, class-specific ID number.

Your most difficult parameter looks to be #3:

The teacher should not be able to know who attended the lessons and who didn't until the end of the term.

This is not realistic, even in a large class.  You are asking a teacher not to remember faces and not notice empty seats.

At the end of the semester when grading, he sorted out the numbers and names and assigned attendance grades, etc.  It worked, and it was fast. Come to think of it, you could use public-key cryptography to have the instructor(s) sign the completed attendance document, thereby giving you non-repudiation for that too.


Why isn't a table used to solve the large number factoring problem? Lots of modern encryption (RSA comes to mind) are based on the fact that factoring large numbers is hard. However, multiplying large numbers is much easier, and table lookups are very easy. Since these large numbers are semiprimes (in all encryption methods I can think of, anyways), why not just make a table of the products of a bunch of primes and use a lookup to find some large number's prime factors? Would such a table just also be computationally expensive to make? Or too big to store or search through or something?


Usage of Fermat primes in RSA Why are Fermat primes ($2^{2^n}+1$) useful as $e$ (the public key) in RSA encryption?

I understand why $2^n+1$ primes are useful, because they would simply be 100...001 in binary, which for computers is faster in calculations. But why is it important that the exponent is also a power of 2?

All primes of the form $2^n+1$ have the form $2^{2^n}+1$.

As the wikipedia article on Fermat numbers says:

  If $2^n + 1$ is prime, and $n > 0$, it can be shown that $n$ must be a power of two. (If n = ab where $1 ≤ a$, $b ≤ n$ and $b$ is odd, then $2^n + 1 = (2^a)^b + 1 ≡ (−1)^b + 1 = 0 \pmod{2^a + 1}$. See Sec. 5 for complete proof.) In other words, every prime of the form $2^n + 1$ is a Fermat number, and such primes are called Fermat primes.

The only known numbers with this format are 3, 5, 17, 257 and 65537.


Is it acceptable to add a setup algorithm in the public key encryption? I saw in the paper How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions at page 29 that key generation algorithm of PKE can use a common random matrix $A$.

Is it OK to add a setup algorithm that generates some common public parameters?

Yes.

There are a lot of precedents, for example DSA of FIPS 186-4 has a setup algorithm, described in appendix B.1.


Is there a secure source of entropy on a typical microcontroller? On a device that does not have a hardware RNG, what is the best source for entropy?

Some options and pitfalls floating around:

Use the ADC to read something analog: can become deterministic if there is access to power supply or some ADCs are just too stable even at LSB.
Use un-init SRAM: power supply brownout attack?
Use crystal jitter:  idea here is to sample the variance between the RTC and MCU crystals and use LSB.

Most microcontrollers that are suitable for crypto I've seen have a variant with a hardware RNG. For example the PIC32 series by Microchip.

However, if not, what you could do is attaching some sensor to an ADC. It would depend on your environment what kind of sensor you could use. It can be anything, which is not easily manipulated (at least not in the LSB(s)).

Then, take the LSB(s) from the ADC, or better yet, use a randomness extractor. How often you can fetch me bits, and how many you can fetch at a time, depends on the ADC, the sensor and the environment, and the security level you want to reach.

If you can go a bit further than just your microcontroller, there are some small hardware circuits that can be used to create randomness. One example is using a diode's avalanche effect.

  Avalanche noise is the noise produced when a junction diode is operated at the onset of avalanche breakdown. It occurs when carriers acquire enough kinetic energy under the influence of the strong electric field to create additional electron-hole pairs by colliding with the atoms in the crystal lattice. If this process happens to spill over into an avalanche effect, random noise spikes may be observed.

In short, we can use a diode with some external circuitry to create random noise spikes. If we then amplify that signal and feed it to a comparator, we get a random bit string.


Could RSA keypairs be used for cryptocurrency addresses? A bitcoin address is created from an ECDSA keypair. It is common to use use a hashed version of the public key as the shared address, but the original bitcoin implementation also allowed for using the unaltered key directly. (which anyway is revealed when the coins in the address is spent) The purpose of public key cryptography here is that the owner can prove ownership of the address by a digital signature, which is required by the blockchain before accepting spending of the coins in an address.

The ECDSA algorithm is not suited for encrypting messages. If an RSA keypair was used it would allow the sender of money to encrypt and convey some personal information to the receiver (eg. by a public message server), which obviously could be a useful feature. Is there any reason why an RSA keypair should or could not be used for cryptocurrency addresses?

You could do this, but you'd have to replace 32-byte public keys by 256-byte public keys and 64-byte signatures by >=256-byte signatures in the storage format, assuming you used 2048-bit RSA moduli.  There are techniques for compressing RSA signatures, but I've never heard of anyone implementing them, so you might be on your own to write the code, and they won't beat 32-byte keys and 64-byte signatures at a remotely comparable security level.  And, unlike ECDSA, RSA key generation is sloooooooooooooooooow.

Alternatively, you could use a Schnorr-style signature scheme, such as Ed25519, with size and computational cost comparable to the ECDSA over secp256k1 as used by Bitcoin, and then reuse the key pairs for ECDH/ECIES, like XEdDSA does.  There is no shortage of ways to shoot yourself in the foot designing and implementing a bespoke cryptosystem, but the combination of EC-Schnorr and ECDH with the same key pairs does not necessarily seem to hurt security in itself.

(Whether you can do this with ECDSA, I leave this as an exercise for the reader to study.  I'm not aware of literature on it; if you find any, please answer fgrieu's question on the subject!  But your time is probably better spent just using XEd25519 than fussing with ECDSA.)


In what way is KeeLoq a block cipher? I'm just going by this diagram of KeeLoq encryption and it resembles these diagrams of Crypto-1 and Hitag2. I'm wondering how it is a block cipher. If it is one and that diagram represents most or all of its design, then it is a very exotic block cipher.

KeeLoq works on 32 bit blocks as opposed to arbitrarily-sized inputs. This by definition makes it a block cipher.

There's even this from the first paragraph of Microchip's description:

  KEELOQ is a proprietary block cipher based on a block length of 32
  bits and a key length of 64 bits.

edit: the diagram is rather unclear. The input and output both end up in the 32 bit register (NLFSR) and the key goes into the 64 bit register (FSR).

For a clearer diagram, see pages 3 and 4 of this Keeloq cryptanalysis paper which at least gives some temporal dimension to the diagram.


Are there any bijective one-way functions not based on number-theoretic hardness assumptions? I'm trying to find a bijective function $y=F(x)$ which should be easy to compute in one direction but hard to compute in the other, where the one-way property is not based on a number theoretic assumption.

The hard direction should be preferably as hard as computing hash preimages, but it could also be that there is only some practical asymmetry (such as taking 1000 times as long to compute one direction than the other).

Poligh-Helmman encryption, LUC encryption and RSA encryption can provide some form of one-wayness since decryption/encryption take very different times, but they are all number theoretic based and require changing the plaintext and ciphertext space to avoid weak plaintexts.

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions.

There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece cryptosystem).

An MQ scheme typically consists of a low-degree invertible polynomial transformation $S$ (public or secret) and two secret affine transformations $A_1,A_2$. The public key is exposed a polynomial(s) $A_2(S(A_1(x)))$. There are many insecure candidates for the nonlinear layer (see survey in this paper), but it is generally assumed that the HFE cryptosystem with sufficiently large parameters is secure.

The code-based cryptosystems hide the generator of some linear code in a similar manner by multiplying it by properly chosen matrices and expose the public key as a matrix.

Both families produce terribly large public keys up to several megabytes, and are of limited use because of that and the lack of systems that withstood a lot of cryptanalysis (except for the original McEliece proposal).

UPDATE:
You may also want to look at some bijective polynomials suggested in the recent algebraic papers. I do not know if there exist efficient inversion algorithms.

For example:
$\left(X^{2^k}+X+a\right)^{-l}+X$ over $\mathbb{F}_{2^n}$, where $n/\text{GCD}(n,k)$ is odd, $l(2^k+1)\equiv 2^{n/2-1}\pmod{2^n-1}$, Tr$(\delta)=1$ in this 2010 paper

For odd $p$: $\left(X^{p^k}-X+a\right)^{\frac{p^n+1}{2}}+X^{p^k}+X$ over $\mathbb{F}_{p^n}$ in this 2012 paper.


How to calculate size of a codebook lookup table to break block cipher? I was reading a book called Serious Cryptography. There is a page saying that block size must be large enough to prevent codebook attacks:

When 16-bit blocks are used, the lookup table needs only 2^16 × 16 = 2^20 bits
of memory, or 128 kilobytes. With 32-bit blocks, memory needs
grow to 16 gigabytes, which is still manageable. But with 64-bit
blocks, you’d have to store 2 70 bits (a zetabit, or 128 exabytes), so
forget about it. Codebook attacks won’t be an issue for larger blocks.

Where is the 2^16 * 16 coming from? I think it's supposed to be 2^16 + 2^16 the sum of ciphertext possibilities and the sum of plaintext possibilities that match this specific ciphertext, right?

Where is $2^{16}\cdot16$ bits coming from?

The $2^{16}$ term is the number of possible 16-bit blocks. The $16$ bit term is the space needed to store a block (that can be a block of ciphertext, with the plaintext used as index; or vice versa). The two are multiplied to get the total size, much like the price for $n$ things is $n$ times the price for one thing.
If we added the number of plaintexts and ciphertexts blocks, we'd get a number of blocks, not a size. And while we need to be able to manipulate all the plaintexts and all the ciphertexts, we do not need space to store both all the plaintexts and all the ciphertexts: one kind comes for free as the index of the table, which uses no space. Much like if we want to store what output from 0 to 9 correspond to input 0 to 9, we need 10 digits (like 8730629415), telling that 0 corresponds to 8, 1 to 7, 2 to 3,… 9 to 5; rather than 20 digits.
In this table of $2^{16}$ values, there are never two identical values. That makes it slightly compressible, down to $\log_2((2^{16})!)$ bit, a 9% saving.
Such a table needs not cover all plaintext/ciphertext pairs to be useful. A much smaller table can allow some attack. For example, a table with $2^8$ entries instead of $2^{16}$ allows decryption of about one block out of $2^8$.


What is the difference between chosen-plaintext attack and adaptive-chosen-plaintext attack? I've just dived in cryptography and would like to learn basics of this science.

Currently I can't understand the difference between these two types of attacks. As I understood from Bruce Schneier's book "Applied Cryptography", adaptive-chosen-plaintext attack is similar to chosen chosen-plaintext attack, but cryptanalyst can modify his choice (plaintext) based on previously got result.

What does this suppose to mean? In chosen-plaintext attack cryptanalyst also is choosing the plaintext. So what is the difference?

With chosen-plaintext attack, the attacker is allowed to choose an arbitary amount of plaintext to encrypt. After that he/she can't do that again, he/she has to work with the current data.

With the adaptive-chosen-plaintext attack, he/she can do the same as with the chosen-plaintext attack, but is also allowed to encrypt new data after the attacker has looked and analyzed previous encrypted bits. He/she can, based on the already encrypted data, choose new data to further advance his/her attack.


Are Blind Signatures Fundamentally Different From Signatures of Hashed Values? I've been reading up on blind signatures and am trying to wrap my head around the concept - specifically in the context of anonymous blockchain transactions using vouchers.  One particular issue I'm having with this is understanding what precisely a blind signature consists of.  Do these differ from signatures of hashed values?

Would the following qualify as a blind signature:

Someone (A) hashes some data and signs it.
Hash sent to another party (B) who also signs it.
Data and hash and signatures are sent to yet another party (C) who can verify it all.

Or are they meant to mean that A creates data and blinds it, B signs the blinded data saying A created it and/or was authorized to do so, C receives blind signature and data without being able to relate it back to A - but by way of B can tell the data was created in a valid manner?

Is the objective just for C to never know who A is, but confirm that it was created in a valid manner via B?

The idea behind a blind signature is that party $\mathcal{A}$ has a message $m$ that they want party $\mathcal{B}$ to sign, but they do not want party $\mathcal{B}$ to learn the value of $m$. Using RSA, where $(e, N)$ is $\mathcal{B}$'s public key and $d$ is it's private key, this may look like:

$\mathcal{A}$ computes $x = m*r^e \mod N$, where $r$ is a randomly sampled value.
$\mathcal{B}$ signs $x$ i.e. $y = x^d \mod N$ and sends the signature to $\mathcal{A}$.
$\mathcal{A}$ computes $s \equiv y * r^{-1} \equiv (m * r^e)^d * r^{-1} \equiv m^d * r * r^{-1} \equiv m^d \mod N$, which is $\mathcal{B}$'s signature of $m$.

Note that $\mathcal{A}$ now has a signature from $\mathcal{B}$ on $m$, and $\mathcal{B}$ has no knowledge of $m$ since they cannot recover $m$ from $x$. [1] Anyone can verify this signature using $\mathcal{B}$'s public key.

Note that this does not work with hashing, because hashing is one-way. If we say $x = H(m)$ then in step 3. we have no way of recovering the signature for the original value $m$.

[1]: as poncho points out, blind signatures have a stronger property than this, namely that if $\mathcal{B}$ signs messages for both $\mathcal{A}$ and $\mathcal{C}$, then given an unblinded message and signature pair $\mathcal{B}$ cannot determine who the signature was for


Understanding WPA2 authentication in details As far as I know, WPA2 authentication consists of a 4-way handshake. The first message is from the AP, containing the ANounce, a random number generated by the AP, The second message is from the client, containing the SNounce concatenated with a MIC of the ANounce, the third is from the AP containing the GTK concatenated with some MIC and the last is simply an ack.

In the case of PSK, PMK = PBKDF2(HMAC−SHA1, PSK, SSID, 4096, 256). So supposing I have psk = "personal-key" and ssid = "net-name", the function would be  PBKDF2(HMAC−SHA1, "personal-key", "net-name", 4096, 256)

   4 iterations of 4096 hmacsha1 xor chains concatenated to form 256b

I do not understand though how the PTK is generated. According to this question, PTK is generated from HMAC-SHA1 of length 512 of PMK as key and (ANounce || SNounce || AP MAC || Client MAC) as text, but how can it generate data of 512b length if SHA1 only outputs 160b? Isn't HMAC-SHA1 equal to SHA1(key XOR opad || SHA1(key XOR ipad || text))?

My second problem is how MICs are computed. I know that they use some message and a key. In WPA2 case, the key is the KCK, the first 128b of PTK, but what is the algorithim used in the computation?

And the third problem is how GTK generated and what is the message inside de MIC that is sent on the third message.

The following answers are taken directly from the 802.11 standard (2012 version).

The PTK is generated as follows:
$$\mathrm{PTK} \gets \operatorname{\mathrm{PRF-X}(PMK, ``pairwise \ key \ expansion", \\
min(AA, SPA) || max(AA,SPA)|| \\ min(ANonce, SNonce) || max(ANonce, SNonce)) } $$
where $\mathrm{AA}$ and $\mathrm{SPA}$ are the MAC addresses of the Authenticator and Supplicant, respectively.  The pseudorandom function $\operatorname{\mathrm{PRF-X}}$ is defined as follows for $X = 128,192,256,384,512$:

PRF-X(K,A,B):
   for i = 0 to (X + 159) / 160:
       Z = Z || HMAC-SHA1(K, A || 0 || B || i)
   return LeftBits(Z,0,X)

The MICs are computed using either HMAC-SHA1-128 or AES-CMAC-128 (which one to use is negotiated during the handshake).
The GTK is simply chosen at random by the AP.


Is this a secure method of encrypting with authentication? My goal is to allow two clients to send files securely over an untrusted network without the need for more than one block of information to be sent. Both clients have ECDSA keys of size 256 bits. I'd like to stress that this is purely for fun and to learn elliptic curve concepts. This will not be used in a serious environment. That being said, here's the protocol design:

Generate a random ECIES value using a random private number and the reciever's public key. Call the resulting key "Key" and the public ECIES value "ECIESPub".
Calculate the sha256 hash of "Key + filecontents" where + is concatenation and sign it with your ECDSA key. Call the result "Sig".
Encrypt the file contents with Key using AES-256-CFB. Call the result "Encrypted" and the IV of the algorithm "IV".
Create a new file with the original file name with ".enc" appended. (dual extensions is acceptable) Write "ECDSAPublicKey + ECIESPub + IV + Encrypted + Sig".
Send this file to the recipient. eg. through skype or email.

On the reciever's end:

Calculate "Key" using "ECIESPub" and your own private ECDSA key.
Decrypt "Encrypted" with "Key" and "IV". Write the result to a new file with the filename of the received file with ".enc" simply removed.
Calculate the sha256 hash of "Key + DecryptedFileContents" and verify it with "Sig" and the sender's ECDSA public key.
If the signature is valid, display a fingerprint derived from the sender's public key for the reciever to compare with their record of fingerprints. If the signature is not valid, display a warning to the reciever. In neither case will the sender gain any information about the success or failure of verification.

Note: I include the key in the generation of the signature to prevent an attack where an attacker can switch out the public key and signature with their own without changing or knowing the secret shared key, on the condition that they know the plaintext. I don't know how practical this attack is, but I thought it was best to combat it.

Are there any glaring holes in this construction that I'm missing?

Quick edit: I realize I'm reusing a key for signing and encryption, however, the main concern about this is the occasional legal requirement to give up an encryption key. If that happens, the reciever can recalculate the key from the public ECIES value and give that up instead. The sender, however, simply won't have the key anymore as it is randomly generated, used once, then forgotten.

The system you described—essentially, sign-then-encrypt with ECDSA and ECIES—is vulnerable to the following attack:

Alice sends Bob the signed-encrypted message ‘The deal is off.’
Bob removes the encryption layer, getting a signed message from Alice saying ‘The deal is off.’
Bob re-encrypts the message to Charlie.
Charlie verifies the message and thinks Alice has canceled the deal.

The problem here is that the message that Alice signed didn't specify a recipient.  The same attack applies to practical systems like OpenPGP and S/MIME, as noted by Don Davis in 2001.

The mere use of signature is also vulnerable to the following attack:

Alice types ‘what a basket of deplorables the voters are’ into her phone, but accidentally sends it to a journalist Jamal instead of her running mate.
Jamal now has a signed message from the political candidate calling her constituents deplorables which he can show to anyone.
Bob wins the election.

The problem here is that anyone can verify Alice's message, because signatures by design provide third-party verifiability.  (The respect Alice has for the voters may be another problem, and the respect Bob has for democracy, rule of law, and journalists, yet another problem, but let's not make this situation too real lest someone get diced up with a bone saw.)

There's a much simpler system, which is actually what Diffie and Hellman suggested in their seminal 1976 paper.  Assume Alice has published her public key $A = [a]P$ in the telephone book, and Bob has published his, $B = [b]P$.

To send a message $m$, Alice looks up Bob's public key $B$ in the telephone book and computes $k = H([a]B)$ to use with an authenticated cipher $E$ to send the ciphertext $E_k(m)$ to Bob.
On receipt of a ciphertext $c$, Bob looks up Alice's public key $A$ in the telephone book and computes $k' = H([b]A)$ to open the message $m = {E_k}^{-1}(c)$, or drop it on the floor if verification fails.

If the telephone book hasn't been tampered with, $k = k'$ so Alice and Bob can communicate.

If Alice wants to save time for many messages to Bob, she can cache the shared secret $k$ and reuse it many times; likewise Bob.  The only overhead is the authentication in the authenticated cipher $E$.

Bob can't forge a message from Alice to Charlie because Charlie has a different shared secret with Alice.  Jamal can't cryptographically prove to anyone else Alice sent an incriminating message, because any ciphertext that Alice could have made, Jamal could have made too using the same shared secret.

This very simple protocol—and the protocol you proposed—has another issue: if Alice's long-term key $a$ ever gets exposed, anyone who learns it can decrypt any past messages Alice has ever exchanged with anyone.  Modern protocols also do key agreements for each conversation like TLS, or each message like Signal, so that they can quickly erase the keys that would allow a network eavesdropper to decrypt past messages.  If you want a bespoke protocol in an application for which existing systems like TLS are unfit for some reason, you might look into the Noise protocol framework and the Noise Explorer, a tool to automatically verify security properties of custom instances of Noise.


Encryption time in ECC In RSA, encryption time is usually much less than decryption time due to having a small public exponent. Can this be achieved in Elliptic Curve Crypto (ECC)?

Actually, there is one way which you can achieve a similar effect: if you have some idle time beforehand, you can perform some of the work even before you know the message you'll encrypt (or possibly even before you know the public key you'll be sending to -- you will need to know the curve).  This doesn't decrease the total amount of work; however it can decrease the amount you work you need to when you get the message (because you did some of that work beforehand).

For example, let us assume you use ECIES; there, you pick a random number $r$, and compute the point $rG$ (where $G$ is the curve generator).  You can do this before you know either the message or the public key you'll be sending to.

Then, when you get the message and the public key $P$, then you compute $rP$, generate the symmetric keys, and encrypt and MAC the message using the symmetric keys; then you package up the values $rG$ and the symmetric ciphertext -- this part is about half the amount of work you'd need to do without precomputation.

Now, this as stated doesn't really address the question (because it doesn't make the work less than the decryption part) -- however, if you also knew the public key $P$ first, you could move the computation of $rP$ into the precomputation step as well, and that would make the remaining part of the encryption (which is just playing around with symmetric ciphers) significantly less than decryption.


Carmichael number factoring Unsure whether this is the right forum for this question, worth a try.

The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many resources on the web states that this is easy, however, without further explanation why that is?

Furthermore, since miller-rabbin exits when a nontrivial square root of 1 is found, this can be used to find a factor to the carmichael number: $x^2 \equiv 1 = (x+1)(x-1)\equiv0\ mod\ N$, where N is the carmichael number we want to factor. Hence factors must be found using $\gcd(x+1,N)$ and $\gcd(x-1, N)$, correct?

Due to problems with strong liars, in some cases we will miss out on factors, is this a major problem? Since miller-rabbin tests only passes composites with a probability 1/4 is it correct to say that the chances of finding a factor is > 0.5?

Kind regards!

Yes, using Miller-Rabin with a random witness does give a practical factoring method.  When you run the Miller-Rabin algorithm, it can end in one of three ways:

The final value is not 1; this case causes Miller-Rabin to output "Composite"
An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite"
The initial value was 1; or an intermediate value was N-1; this causes Miller-Rabin to output "Probably Prime".

Case 1 will happen only if $W^{N-1} \neq 1 \bmod N$, however, that we get that inequality for Carmichael numbers only if $W$ is a multiple of a factor of $N$; in this case, $gcd(W, N)$ gives us a nontrivial factor.

For Case 2, well, that gives us a nontrivial value $X$ for which $X^2 = 1 \bmod N$; as you correctly point out, a nontrivial square root of $N$ immediately gives us the nontrivial factors $gcd(X+1, N), gcd(X-1, N)$

Hence, in the specific case of Carmichael numbers, if the Miller Rabin test outputs "Composite", we always have enough information to immediately factor.  And,  when Miller-Rabin is given a composite number, then it will output "Composite" with probability > 3/4; hence, a single iteration will allow us to factor with high probability.

In fact, for Carmichael numbers, the probability of success with Miller Rabin is actually > 7/8; Carmichael numbers are not the worse case for Miller Rabin.

This gives us a practical factorization method; however for pedantic reasons, it doesn't actually answer the question.  It's not a poly-time algorithm; it is a probabilistic poly-time algorithm which, per iteration, has a good probability of yielding a factor, but it also has a probability of not finding a factor.


Why do Problems for Post-Quantum algorithms have to be NP-Hard? The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.

Solving quadratic equations over finite fields
short lattice vectors and close lattice vectors
bounded distance decoding over finite fields

At least the general version of these is NP-complete
I am asking myself why these mathematical problems need to be NP-complete (in the general version) and how this is even useful, when instances are used that are not NP-complete

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem.
The story is rather simple, but also technical.
Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case LWE problem in dimension $n$, standard deviation $\sigma$, and moduli $q$.
Regev's quantum worst-case to average-case reduction for LWE states that:
$$\mathsf{SIVP}_{\tilde{O}(nq/\sigma)} \leq \mathsf{LWE}[n, \sigma, q]$$
Where $\mathsf{SIVP}_\gamma$ is the short independent vectors problem (think of it like a generalization of the shortest vector problem to finding $n > 1$ short linearly independent vectors, where $n$ is the dimension of the lattice).
Note that the $\gamma$ here is an approximation factor that is allowed in the problem.
What is the precise complexity of $\mathsf{SIVP}_\gamma$?
This highly depends on the parameter $\gamma$, but the following should suffice for this post.
It is known that $\mathsf{SIVP}_{\tilde{\Omega}(\sqrt{n})}$ is in $\mathsf{AM}\cap co\mathsf{AM}$.
This implies that it is not $\mathsf{NP}$-hard unless the polynomial hierarchy collapses to some finite (it looks like 2nd?) level, which complexity theorists view as being unlikely.
This essentially means that while $\mathsf{SIVP}_\gamma$ is known to be NP-hard for some $\gamma$, the $\gamma$ used in lattice cryptography is such that we view it as extremely unlikely that $\mathsf{SIVP}_\gamma$ will be NP-hard.
Still, for basic protocols one can generally take $\gamma$ to be some small polynomial, so $\mathsf{SIVP}_\gamma$ is "close" to an NP-hard problem, especially as the smallest approximation factor that we have polynomial-time algorithms for is something sub-exponential iirc.
More generally, NP hardness is the wrong thing to look at in cryptography.
What people actually want is some notion of average-case hardness.
In lattice cryptography one can formally connect that with worst-case hardness, but not every area in cryptography has such reductions.
In areas that don't, the particular worst-case hardness of the problem is not very important --- a problem can have some instances that are very hard while still being bad for cryptography, as it may be hard to generate a hard instance.
What is more important is specifying some plausible average-case hard distribution and examining the particular hardness of this.


Identifying a bad public key The great thing about public key cryptography is that anyone can generate a keypair, keep the private key secret and publish the public key anywhere they want.  This is used in CAs where an administrator presents a CSR containing a public key and gets a certificate back with the same public key signed.  It's also used by Github to allow users to do Git operations via SSH.

Both asymmetric keys and passwords can thus used as a credential.  There's a lot written about best practices for passwords, but I was wondering if there are also similar best practices for asymmetric keys?  Length is a factor of course (the internet tells me that my RSA key should be at least 2048 bits and that my ed25519 key should be at least 256 bits).  Still, even when a key has the correct length, it may be generated by a bad random generator (Debian key).

Do (should) services where the customer has to provide a public key, check this public key for weaknesses? What kind of weaknesses could a key be tested for?  How would you test for these?

Some tests that I think might be useful:

The bit length is appropriate for the algorithm the key is used for (best practices?)
The key is not a known compromised key (public databases?)
The key is not generated using a bad random generator (how would you test this?)

Do (should) services where the customer has to provide a public key,
  check this public key for weaknesses? What kind of weaknesses could a
  key be tested for?

I'm pretty sure that there's no easy way to find out if a public key has been generated safely without some sort of brute-force attack.

Ultimately I think it's up to the creator of the public key to make sure that the generated key has been created in an orderly fashion, i.e. by using a secure CSRNG. So services should probably not check public keys provided by customers for weaknesses.

The three tests that you have listed are generally good ways to check for possible weaknesses (if you would want to do so). Your second point though (The key is not a known compromised key (public databases?)) might be very inefficient, depending on how large such a public database could be.

  How would you test for these?

The bit length is appropriate for the algorithm the key is used for (best practices?)

A list of recommended key lengths: BlueKrypt.

The key is not a known compromised key (public databases?)

If the database consists of the factors (in case of RSA), you could just try to divide a public key with all these factors and see if it results in a whole number. If the database only consists of public keys (in case of RSA), you could use the Euclidean algorithm and go through all keys in the database.

The key is not generated using a bad random generator (how would you test this?)

Unknown, unless you know which tool was used to generate the key.


Is it insecure using addition instead of multiplication in Elgamal encryption? I am wondering why most textbook only explain Elgamal encryption using multiplication operation, i.e. $c = m\cdot g^{ab} \pmod p$ instead of addition modulo $p$, i.e. $c = m + g^{ab} \pmod p$?

Is there any flaws or insecurity for the addition version of ElGamal encryption?

In the generic sense of an abstract group, this is a problem since addition may not be defined. However, when working modulo a prime $p$, addition is certainly defined. However, it is not secure. In order to see why, note that we must work in a prime subgroup of $p$ in order for ElGamal to be secure. Thus, we typically choose $p=2q+1$ where $q$ is also a prime, and then we work in the subgroup of order $q$ of quadratic residues. When you add, you may get out of the subgroup.

A description of an attack when addition is used A Simple Attack on ElGamal Public Key Encryption by Dan Boneh (the paper deals with something else, but also considers addition as motivation).


What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions) I am studying Pseudorandom Number Generators and when reading the discussion on One-Way Functions and Hardcore Predicates, I came upon this equation.

$$b(x,r)=\displaystyle \bigoplus_jx_jr_j$$

I understand that the $b(x,r)$ is the hardcore predicate (either a $1$ or $0$) but I do not understand the operation being performed here. Specifically, I have never before seen the XOR symbol ($\oplus$) used in this way and do not understand what it signifies. Is it the sum of the values found by XORing $x_j$ and $r_j$? $\bmod 2$?

Assume $x$ and $r$ are bit strings of same length and $x_i$ and $r_i$ denotes the $i$-th bit of $x$ and $r$ respectively. The operation performed between $r_j,x_j$ is multiplication which is equivalent to AND ($\wedge$) as they can both only take the values $1$ or $0$.

Generally any large symbol like $\displaystyle\sum_jf(j)$, $\displaystyle\bigwedge_jf(j)$ and $\displaystyle\bigoplus_jf(j)$ applies the operation denoted by the large sign "between" each iterated value of $f(j)$, resulting in $\displaystyle\sum_jf(j)=f(j_1)+f(j_2)+\dots$, $\displaystyle\bigwedge_jf(j)=f(j_1)\wedge f(j_2)\wedge\dots$ and $\displaystyle\bigoplus_jf(j)=f(j_1)\oplus f(j_2)\oplus\dots$.

So the formula you gave can be read as follows:
$$b(x,r)=\displaystyle\bigoplus_{j}x_jr_j=\displaystyle\bigoplus_{j}x_j\cdot r_j=x_0r_0\oplus x_1r_1\oplus \dots=(x_0\wedge r_0)\oplus(x_1 \wedge r_1)\oplus\dots$$.