Decrypt Base64 Encoded Monoalphabetic Cipher I'm attempting to decrypt a body of ciphertext which has been encrypted using a monoalphabetic cipher. The trouble I'm having is that the plaintext was base64 encoded before being encrypted. In this puzzle the encryption scheme uses an array containing a permutation of 0-63 as the key. It takes the plaintext and encrypts each char by taking its index in the base64 alphabet and using that as the index in the key. Then that key value  is used as an index to take the ciphertext character from the base 64 alphabet.

I understand the typical way to solve a cipher like this is through frequency analysis of the letters (knowing that e is the most common letter and so on). My confusion comes from how to do this given the plaintext is base64 encoded.

I have read though this post but am having trouble understanding how to actually apply it. I have been able to write some python to count the frequency of every 4th char in the ciphertext but I'm not sure what the next step is to get the plaintext/key.

One of the things I did attempt was mapping the results of the frequency analysis back to plaintext. For example e in binary yields 01100101. Then if you have an e as the 3rd char in the plaintext then the 4th char of the base64 encoded plaintext would be l (100101). From there I would look at the analysis of the ciphertext and see the most common letter was V meaning that V mapped to l. Then calculating the different in indexes in the base 64 alphabet of those to letters I get
$$64 - 37 = 27$$
(37 = the index of l, to get to the end of the alphabet)

$$27 + 21 = 48$$
(adding 21, the index of V).
This leaves me with the $key[30] = 48$, 30 being the index of e in the base64 alphabet. I repeated this for multiple letters but it didn't yield any readable text when attempting to decrypt with that key then unencoding the returned text.

Additionally I attempted to map the capital and lower case letter to the same result since I believe this will just yield a case insensitive plaintext. Continuing the example above, I would also set $key[4] = 48$ as well, 4 being the index of E in the base64 alphabet.

I'm not sure if this is signifigant but all the indexes in they key array that I did not map (some of the less common letters, 0-9, and '+' '/' I initialized to 0.

Any tips on where to go from here or how to approach this problem would be greatly appreciated.

You will probably not get any (even partially) readable text out until you've figured out the decryption of the most common characters in at least two adjacent base64 positions (1 and 2, 2 and 3, or 3 and 4).

That's because the eight bits of each plaintext byte get spread across two adjacent six-bit base64 characters during the encoding process.  Thus, even if you manage to correctly decrypt one of these two characters, you've still only recovered at most six of the eight bits.  That leaves at least two bits whose value you'll just have to guess.

That said, the difficulty of guessing those two missing bits depends a lot on which bits happen to be missing.  In particular, the ASCII codes for all letters (A-Z, a-z) have their highest two bits out of eight set to 01.  (The third-highest bit is 0 if the letter is uppercase, and 1 if it's lowercase.)  So, if your plaintext is actually ASCII text, you may be able to get some partially readable output just by trying to decrypt the last base64 character in each group of four, and just assuming that the previous character decodes into something that ends in the bits 01.

(However, do note that the most common plaintext byte, if your plaintext is indeed ASCII text, is most likely not a letter at all, but the space character, whose ASCII code 32 = 00100000 in binary begins with 00, not 01.  The same is true of numbers, line feeds and most but not all punctuation.)

More generally, you will likely want to exploit the structure of the ASCII code, which makes the highest two or three bits of each plaintext byte quite predictable.  In particular, if you take any group of three eight-bit plaintext bytes (representing three ASCII characters) and split them into four groups of six bits (as base64 encoding does), you'll end up with something like this:

ABC??? ??DEF? ????GH I?????

where the bits ABC, DEF and GHI (corresponding to the highest three bits of each plaintext byte) can be:

000 only if the byte represents a control character (of which the only ones likely to appear in plain ASCII text are the line feed = 00001010, the carriage return = 00001101, which is usually always followed by a line feed, and possibly the tabulator = 00001001);
001 for spaces (00100000), numbers (for which the next bit is always 1) and most punctuation characters;
010 for uppercase letters (and the characters @, [, \, ], ^ and _); or
011 for lowercase letters (and the characters `, {, |, } and ~).

Note that, in plain ASCII text, the highest bits of each eight-bit byte (i.e. bits A, D and G above) are always 0.  (That said, they could be 1 if your plaintext was actually written in some "extended ASCII" encoding like ISO Latin 1, or perhaps Unicode in the UTF-8 encoding, and contained some non-ASCII characters.)

For example, let's say that you guess that the most common byte in your plaintext is probably an ASCII space (binary 00100000), and therefore that the most common base64 character (let's arbitrarily say it's X) at the end of each 4-character group probably encodes the bits 100000.

This means that this base64 character X should basically never appear as the first character of a 4-character group (since that would make bit A above 1), and should only rarely appear as the second character (since that would make bits DEF be 000, which should be pretty rare unless the plaintext is full of line breaks).  If that's indeed the case, you can be pretty confident that you've guessed correctly.

Also, you can then look at the base64 characters that precede X in the ciphertext, and be pretty sure that they all represent six-bit base64 codes that end in 00 (since bit G must be 0 in ASCII text anyway, and if bit H was 1, that would decode to the rather uncommon plaintext byte 01100000 = `), which (together with their frequencies in the four different positions) should help narrow down their possible values.

Similarly, you can guess that the most common base64 character in the first position of a four-character group probably encodes the bits 001000, and that the two most common characters following it in the second position probably encode 000100 and 000101 (assuming that a space is most often followed by a lowercase letter; of course, the bit sequences 000110 and 000111 are also likely to be fairly common, since they arise from a space followed by an uppercase letter).

And the most common base64 character in the third position most likely represents the bits 000001 (i.e. a space followed by a letter), especially if it does not usually precede the most common fourth-group character (i.e. X above), as that would again yield a rather unlikely plaintext sequence involving the backtick character ` = 01100000.*

Also, assuming that your plaintext is indeed English ASCII text, another approach you can use to get started is to look for common repetitive sequences of base64 characters in the ciphertext, and assume that they likely correspond to common sequences of characters in English text.

For example, probably the most common five-byte sequence in English ASCII text is  the  (i.e. "the" surrounded by spaces on both sides).  When broken up into three-byte groups for base64 encoding, depending on where the group boundary happens to fall, you can end up with either:

 th and e ?;
? t and he ; or
?? , the and  ??,

where ? stands for some variable byte (most likely a letter).  Thus, the 4-character base64 groups encoding  th, the and he  should all be pretty common, and appear with roughly the same frequency (although note that the frequencies can be skewed not only by random chance, but also by the presence of other common English words sharing the same beginning or end, such as "that", "this", "those", "these", "they", "there" and "then", as well as "he" and "she", and of course the capitalized form "The").

Furthermore, you can distinguish the base64 groups encoding these different 3-byte sequences by looking at the surrounding encrypted base64 characters.  For example, the group that encodes the should very frequently be preceded by the base64 character that encodes the lowest six bits of an ASCII space (i.e. 100000) and followed by the base64 character that encodes the highest six bits of an ASCII space (i.e. 001000).  Furthermore, since they encode spaces, which are common in general, these two base64 characters should usually each be the most common ones in that position of a 4-character group.

(Of course, the group the won't always be preceded or followed by a space, since it can also appear as part of a longer word, or possibly at the beginning or the end of a line.  But the most common plaintext bytes before and after it should still be spaces.)

Similarly, the four-character group encoding  th should begin with the base64 character that encodes the first six bits of an ASCII space (and is thus rather common in the first position of a group), and should be commonly followed by a specific sequence of three base64 characters that encodes e  followed by a letter.  And, correspondingly, the group that encodes he  should end in the common character that encodes the last six bits of a space, and should typically be preceded by the two base64 characters that correspond to  t at the end of the previous group.

Some other fairly common byte sequences in English text that you may want to look for include  a  and  I  (i.e. "a" and "I" surrounded by spaces), both of which can be quite easy to recognize if you've already determined which base64 characters corresponding to spaces at the beginning and the end of a group, as well as  and  (another fairly common three-letter word surrounded by spaces, occurring in a similar pattern as  the  above, but typically sufficiently less common to be fairly easily distinguishable) and the four-byte sequences  to ,  of ,  in ,  at , etc.  You'll probably want to mostly ignore the latter until you've managed to decode at least some common letters, though, since there are rather many common two-letter words in English, and their relative frequency can vary a lot based on the topic and style of writing.

*) That said, everything always depends on what the plaintext actually it.  For example, the Markdown source code of this very answer is full of backticks, most often following or followed by a space, since that's the Markdown syntax for inline code.


Is there a simplified article, video, or blog about bulletproofs? I'm trying to learn about bulletproofs for my master "Enhancing Privacy in E-voting Systems", but the original paper was too hard for me. I also tried to look at this, but it was also too difficult. So, is there and article or a video or blog that explains bulletproofs on a beginner's level?

edit: i found this it is easy relatively and start from the basics

I found this blog post on the MIT Digital Currency Initiative's website super informative yet introductory. Hopefully, you find it helpful as well.


Need to generate new DH keys for every message in OTR Going through the OTR specification I don't quite get why a new DH keys (and hence new symmetric key and hmac key) are generated for each message to be sent. Why is this necessary? I don't think it makes the argument for PFS any stronger. Also it does not have anything to do with deniability as well. Am I missing something here?

Well it makes the arguments about PFS stronger.

If they would not frequently do a re-keying and securely erasing the old key (note that then they can not even read their own past messages anymore) an adversary that breaks either into Alices or Bobs computer and gets the shared secret can read and link all the previous communication between Alice and Bob. Re-keying eliminates this problem. If you do a re-keying and key erasure after each message, you have the strongest forward secrecy guarantee (although this may be a bit paranoid - but it does not cost really much either).

Note also that the deniabiliy is only concerned with the MAC keys and does not reveal the encryption keys. If you have the DH shared secret you can recompute all keys (in particular the encryption keys) previously used. Someone other may use a previously published MAC key to generate some MAC for a message (deniabiliy), but note that the corresponding correct encryption key can only be known to someone who knows the shared secret. So the adversary can tell apart original from "faked" messages. The longer you use the same shared secret the longer the conversation history the adversary can reconstruct.


AEAD using AES-CBC and MAC: how to order the input to the MAC I'm writing code to provide an AEAD utility.  It uses AES-256-CBC for encryption and SHA-512(key+data) truncated to 256 bits as the MAC.

encrypt(
    aes_key: byte[32],
    mac_key: byte[32],
    plain_text: byte[],
    aad: byte[],
) {
    iv = crypto_random_bytes(16)
    cipher_text = aes_256_cbc(aes_key, iv, plain_text)
    aad_encoded_length = int_to_little_endian_4_bytes(aad.length);
    auth_state = sha_512(key + aad + iv + cipher_text + aad_encoded_length)
    auth_tag = truncate_bytes(auth_state, 32)
    return cipher_text + auth_tag
}

I'm primarily interested in how to order the data I'm passing to sha_512.  I based it off of this: https://www.ietf.org/archive/id/draft-mcgrew-aead-aes-cbc-hmac-sha2-05.txt

Is that the best ordering?

(P.S. Though not really part of this question, my decision to use AES-256-CBC and truncated SHA-512 was based on library availability, performance, and resistance to accidental nonce reuse.)

This part of the standard (at the end) explains why the length of the authenticated data is at the end, namely to ensure a unique input to the MAC for all pair of ciphertext and authenticated data:

During the decryption process, the inputs A and C are mapped into the
input of the HMAC algorithm.  It is essential for security that each
possible input to the MAC algorithm corresponds unambiguously to
exactly one pair (A, C) of possible inputs.  The fact that this
property holds can be verified as follows.  The HMAC input is X = A
|| C || len(A).  Let (A,C) and (A',C') denote two distinct input
pairs, in which either 1) A != A' and C = C', 2) C != C and A = A',
or 3) both inequalities hold.  We also let X' = A' || C' || len(A').
In cases 1 and 2, X != X' follows immediately.  In case 3, if len(A)
!= len(A'), then X != X' directly.  If len(A) = len(A'), then X != X
follows from the fact that the initial len(A) bits of X and X' must
be distinct.

in your case C is just the IV and remaining cipher text, of course; in the standard IV is explicitly part of the C.


Does the transposition cipher have a network application? So I'm reading a chapter in my networking book, and it talks about substitution and transposition ciphers. I know that most network security uses public key or symmetric encryption, but I wonder whether a simple transposition is also used. I ask because I'm not sure how they would quickly decode the message on the other side. It would seem they would need to use something like the DH Key Exchange, and even then, they could just use the traditional symmetric encryption at that point anyway.

If “transposition” and “substitution” do have applications, what are they and how secure are they?

Transposition and substitution are heavily used in today's block ciphers. S-box means substitution box, and P-boxes transpose bits.

When you say transposition cipher you are referring to classical cryptography.  The heyday of the transposition cipher was before the end of World War I. The ADFGX and the ADFGVX were fractionated transposition ciphers used by the Germans (and broken by the French).  Double fractionation is stronger, especially when at least one iteration is disrupted (VIC cipher). But all of this belongs to the last century because it is now trivial to break classical transposition ciphers.

But transposition itself has not gone away, and modern methods are much better than those of 1918.


PKCS5 having no padding? I am using the javax.crypto.Cipher in Java to do AES/CBC/PKCS5Padding encryption. What I am observing is that, if you try to encrypt a Plaintext with no padding, PKCS5 adds another entire block just to padding. For example, if I got a 32bytes Plaintext, assuming that AES is using 16byte block size, the padding size should be 0. But, instead of that, PKCS5 adds another block for padding.

Is this correct or is just a matter of javax.crypto.Cipher implementation?

Is this correct or is just a matter of javax.crypto.Cipher implementation?

It is correct. You need to always add some amount of padding if you are to distinguish between different padding lengths. With PKCS5 padding the length of the padding is $b - |m| \mod b$, where $b$ is the block size. With $|m|$ a multiple of block size a whole block of padding is added.


Is it overkill to run a key generated by OpenSSL through pbkdf2? I'm generating a key & iv with OpenSSL via:

key = OpenSSL::Cipher::Cipher.new('aes-256-cbc').random_key
iv = OpenSSL::Cipher::Cipher.new('aes-256-cbc').random_iv

Then I am running the random key through:

salt = OpenSSL::Random.random_bytes(32)
OpenSSL::PKCS5.pbkdf2_hmac_sha1(key, salt, 2000, cipher.key_len)

My question being, is this overkill or make the random key generated by OpenSSL weaker? Would it be sufficiently secure to just use the key without running it through a pbkdf2 function?

Any advice would be greatly appreciated.

Thanks!

PBKDF2 is designed for low-entropy passwords. Assuming your key is generated by a CSPRNG, then running it through PBKDF2 is redundant.  I don't, however, believe it could be weaker than the original key.


Should AES-CMAC key cryptoperiod be affected by MAC truncation to avoid birthday-attacks? Given a 128-bit key used for authentication based on AES-CMAC, the NIST 800-38B recommendations suggest at least two criteria for a good key cryptoperiod:

after 'MaxInvalids' error messages the key should be retired (considering the MAC truncation and the accepted Risk in appendix A);
the key should be changed to limit its message span (e.g. $2^{48}$ usages for AES-128).

My question is: should the second criterion be considered if I have MAC truncation?
In my scenario, I'm assuming that the attacker can only see truncated MACs (suppose $30$ bits after truncation). Since I'm using truncation, and this criterion is made to avoid attacks based on detection of a pair of distinct messages with the same  MAC  before  its  truncation, should I still consider this criterion? If yes, should the limit still be $2^{48}$ or is it affected by the truncation?

UPDATE

The scenario is: only truncated MACs are sent to a limited-bandwidth network, and the attacker has access to the network. Considering Elias answer I removed the assumption that the attacker sees only truncated MACs, which is not meaningful. So, if we remove this assumption, do I have to shorten the cryptoperiod to consider $2^{15}$ (truncated MAC), or I can just consider $2^{64}$ (entire MAC)?

Yes, truncated MACs influence the cryptoperiod.

First of all, I cannot really think of any case where it makes sense to assume that the attacker only sees a truncation of the MAC if that isn't what is actually used in the system!
And if you actually truncate your MACs to 30 bits you will probably have collisions after $2^{15}$ message blocks. So you definitely need to reduce the cryptoperiod.

On the other hand you're saying an attacker can only see 30 bits of the MAC because you are truncating it. Let us assume that you are still using the full MAC and that this makes sense in your scenario for some reason.

This in itself doesn't change the attackers position significantly:

Exhaustively searching for the correct key becomes more complicated because now the given 30 bits of the MAC might match but it might still be the wrong key. However there are $2^{128}$ possible keys and by the birthday paradox a MAC collision will probably occur after about $2^{64}$ message block. So this is the more plausible target anyway.
When a collision occurs the attacker can now not readily detect it anymore because only parts of the MAC are visible to him. On the other hand it will potentially be easy to submit fake queries to validate potential collisions and the probability for a collision doesn't change when the attackers view is truncated.

So in this case it would be fine to keep the values but I would love to hear how this makes sense.


AES block cipher modes of operation have a project in which I have to implement an en/de-cryption structure using a standard AES block of 128-bits in VHDL and I think I'm a bit confused. So I'd like to ask some questions about AES and its modes of operation.

When we say that we use a 128-bit key, does it mean that the data input's size is 128-bit or not? Generally can the block size be smaller than key?
A block receives a plaintext. When the same block can receive a new plaintext?
How can I perform each mode to make a system which encrypts information (parallel sequential)? I think that in NIST publication is clearly which modes can be performed pipelined or not. Although, I've been asked to find new ways of performance. What can I do? Please some help.

AES has a 128-bit block size, period. The valid key sizes are 128, 192, and 256-bits.
I am not sure what you mean by that, a "block" is a 128-bit group of data, being the input and output to the cipher, it does not receive anything. Please revise that part of the question, and I will adjust my answer.
CTR, OCB, and ECB are the only modes I know that can run encryption on blocks independent of eachother. CTR is the obvious choice for a fast secure implementation and turns the block cipher into a stream cipher. OCB is a more complex mode built on ECB, where both the input block and cipher output are modified using an incrementing counter generated from a nonce, and provides 1-pass authentication.


Given $g^a, g^b, g^c, g^{1/b}$, is it hard to distinguish $e(g, g)^{abc}$ from a random value? where $g$ is a group element in bilinear group $\mathbb{G}$. I understand it is very similar to the conventional DBDH problem, but $g^{1/b}$ is also known, possibly making it easier? Does anyone know the answer or suggest some material for reference? Thanks.

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem):

  Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$.

Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. Your original problem is to take input $(g,g^a, g^b, g^c, g^{1/b}, Q)$ and decide whether $Q = e(g,g)^{abc}$ or not. After substituting $g = h^b$, we have that the new problem is to take $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and decide if $Q = e(h,h)^{b^3 ac}$.

So, assume you have a solver $S$ for the new problem.  Then we can solve the 2-wDBDHI problem as follows:

Input to 2-wDBDHI is a tuple $(g,g^x,g^{x^2},g^y,T)$.
Sample a random element $z \in \mathbb Z_q^*$.
Call $S$ with input $(g^x,g^y,g^{x^2},g^{x^2 z},g,T^z)$, which will output Yes when $T^z= e(g,g)^{x^3 y z}$, and No otherwise.
Output the result from the last step.

Recall that solver $S$ takes input $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and determines whether the following equation holds:
\begin{align}Q = e(h,h)^{b^3 ac}\end{align}
Take the substitutions $h=g$, $a = y/x$, $b = x$, $c = xz$, and $Q = T^z$, so:
\begin{align}T^z = e(g,g)^{x^3 (y/x) xz} = e(g,g)^{x^3 yz}\end{align}
It is clear that when this equation holds, then $T = e(g,g)^{x^3 y}$ holds too, and vice versa, so this algorithm is a solver for the 2-wBDHI problem.

According to the ECRYPT II report - D.MAYA.6
Final Report on Main Computational Assumptions in
Cryptography, the best known algorithm for 2-wBDHI is to solve DLP in $\mathbb G$, so you can say that your problem is hard.

Note: My previous answer didn't answer your question, since the strong-DDH is not hard when using pairing groups... I was merely stating that your problem is at least as hard as an easy problem (duh!)


Is the cipher "Kalyna" with a 512-bit key length more secure AES with a 256-bit key? Recently I have found out that Ukraine has its own symmetric encryption algorithm "Kalyna". Developers of this algorithm said that their algorithm is more secure than AES because of longer key length and lack of any vulnerabilities by hardware acceleration (like AES-NI in modern processors). Is it the truth, or is AES better?

... their algorithm is more secure rather AES because of longer key length and lack of any tables in hardware acceleration. Is it truth, or AES is better?

More key material

Using more key material does not improve security once you are already using enough key material to be secure.

A 256-bit key is well out of the reach of mankind to crack, even if quantum computers equipped with Grover's algorithm were being used. So using more key material is not productive.

Using more key material can even weaken the security of the design, or at least make the design less efficient.

The more bits you are working with, the longer it takes to diffuse them evenly through the rest of the state. This implies that larger keys (and larger states) need more rounds to achieve complete diffusion.
Insufficient diffusion is one of the leading causes of weaknesses

The goal of algorithm design is basically to hit the ideal balance between efficiency and security. Due to the fact that using excessive amounts of key material will degrade performance for no benefit in security, this raises a flag regarding the competency of the design.

That being said, if you intend to use the cipher to create a hash function, then a larger key size can be useful to compress more data per invocation of the cipher.

Lack of vulnerabilities in hardware acceleration

While it's correct that tables are a potential vulnerability in an implementation, few algorithms require the use of tables. As long as the table is a memoized function and not just an actual random permutation of words, then an implementation can always choose to evaluate the function discretely instead of using a lookup table. Note that if the table were to be an actual random permutation of words, it probably wouldn't provide good non-linearity.

Hardware acceleration is specified explicitly. The AES circuit is supported as a hardware instruction on modern Intel CPUs. It is thoroughly unlikely that this instruction will ever be replaced by Kalina Kaylna. As far as many (if not most if not all) consumers are concerned, the details of hardware accelerated Kalina Kalyna are of little concern and so are a moot point.

If you are concerned that the built-in AES circuit has deliberate vulnerabilities, you are always free to use a software implementation. While AES-NI will obviously be faster, and a softare implementation that uses tables will be fast but vulnerable to side channels, the average consumer probably does not need huge throughput anyways. So if those are a concern, you can always use an implementation that is designed to be resistant to side channel attacks.

Cryptanalysis

If you want cryptanalysis of AES, then you are free to investigate the huge amount of pre-existing research on the subject. AES has been around for years and is probably the single most heavily analyzed symmetric cipher, possibly only second to DES.

If you want cryptanalysis of Kalina, you're almost certainly out of luck. Searching for "Kalina cipher", I could not even find the proposal or definition of the design, let alone any analysis of it. Searching for "Kalina" on eprint.iacr yields no results.

Edit: With the correct spelling of the design, it is possible to locate the specification and there are a few (3) cryptanalysis results on eprint.iacr.

Because few, if any, will ever use it, it is probable that it will never receive any meaningful analysis from competent cryptographers. It is certain that it will never receive the same amount of analysis that AES has received. It is possible that some of analysis that will be performed (e.g. by NSA) will never be made public.


TLS - self encrypting to avoid tls setup, secure? I am in doubt : of course one can create a tl connection between a client and a server.

But what if the client sends self encrypted with, say, blowfish, data to the server? The goal is that the server remains dumb about tls.

The question is not if it is possible, it is.

But in case of a "unattended listening by someone who might love hats", would that be secure enough if the hacker gets the packet?

Would it lessen the security ?

To me, maybe yes, because the hacker would have the packet on his/her computer with the speed involved vs hacking a tls connection. But am I correct ?

Edit : I am new to the security context.

It depends!

Any of the two alternatives TLS or directly symmetric encryption with a pre-shared key will of course require the sender (him/herself) to encrypt the data.

From a cryptographic perspective any statement about security/"being secure" even relative often requires specifity and not much about the actual ciphers are stated. that is why the answer is that it depends.

As much as it depends there are some points which might have some more general application.

TLS will be a stepwise procedure and use first asymmetric encryption (that with public and private keypair) to establish a secure channel. In another step it will then use this rather expensive/slow channel (because it takes more calculation power per transmitted data) to exchange a session key that is used for symmetric encryption. At this point you are at the point at which I assume your suggestion starts and that is that, you have a key only known to the legitimate sender and receiver.

Given that the symmetric encryption following a TLS initial handshake/sessionkey exchange is having the same attributes as the one you suggest with the "self"encrypted setup than there is no reason to see any difference in "security".

Indeed if you know were able to have a shared key for symmetric communication available on both ends of your communication, then this means no need to exchange a session key via asymmetric pub/pri-key encryption in the first place. At best with directly using symmetric encryption any vulnerabilities in the asymmetric part of the TLS can be avoided.


AES parameters specifications I'm writinig manager for all transformations which is described on https://developer.android.com/reference/javax/crypto/Cipher.html

There are few questions about how cryptographic algorithm works.

I found on Wikipedia that AES can have 128, 192, 256 key sizes. But I cannot define sizes for IV.

I got this error:

java.security.InvalidAlgorithmParameterException: expected IV length of 16

So is it mean that for all AES transformations IV should have only one size (128-bit)?

Except ECB:

java.security.InvalidAlgorithmParameterException: ECB mode does not use an IV

I also noticed that AES/CBC/NoPadding doesn't work with any stream (it should be fixed). What the sense of this transformation if it cannot be applied to all data? But it works with any data if I preferred padding. Any explanations?

javax.crypto.IllegalBlockSizeException: error:0607F08A:digital envelope routines:EVP_EncryptFinal_ex:data not multiple of block length

And the last question. For which modes IV is necessary/optional (it seems like necessary (not optional) for every mode except ECB) while encryption and for which is unnecessary while decryption?

Finally I should to create table for every mode (there is 6): CBC, CFB, CTR, CTS, ECB, OFB. Something like:
1. IV: necessary / optional / unnecessary.
2. IV for decryption: necessary / unnecessary.
3. Acceptable IV lengths.
4. Data should multiple of block length: true / false (block length).

So is it mean that for all AES transformations IV should have only one
  size (128-bit)?

No, not really. The acceptable size for the IV is defined by the mode of operation. Some modes require a full block size as the IV (CBC, CTR, ...), others a bit less and again others take just about any length of an IV that you throw at them (GCM, ...).

  What the sense of this transformation if it cannot be applied to all
  data?

CBC works by chaining full blocks together. Thus you need to process a multiple of the block size. Normally if we don't have a multiple of the block size we pad our data to this size, but in this case you chose to disable padding and as such the length restriction applies.

  For which modes IV is necessary/optional?

Any mode that does not take an IV is trivially insecure under standard security definitions. As such it is strongly recommended against using any such mode (like ECB or SIV) unless absolutely neccessary. Every other mode requires an IV. And if you need an IV for encryption you'll also need one for decryption and vice versa.


Definition of the Decryption oracle In the context of public-key encryption, what would be a formal definition of the decryption oracle?

I know the informal definition (i.e., a function that is available to the adversary and that provides the decryption of any ciphertext of her choice, except for the challenge ciphertext), but I am looking for a formal definition. I have checked some reference textbooks and papers and it is usually defined informally, just before (formally) defining chosen-ciphertext attacks. I am specially interested in a multi-user setting, since I will later be working on definitions of security for proxy re-encryption, but I want first to fully understand the concepts for the case of PKE.

The motivation behind this question is that I don't know if it is necessary to specify the underlying public-key in the oracle query or if it is something implicit. For instance, let us assume that the adversary creates ciphertext $c_1 = Enc(pk_1, m)$. Is it assumed that the decryption oracle should answer the query $\mathcal D(c_1)$, even if the public key used is not specified? In the case that the decryption oracle permits to specify the associated public key, would it be valid the query $\mathcal D(pk_2,c_1)$? That is, trying to "deceive" the decryption oracle into decrypting with a different key.

In the standard definition of security for public key encryption schemes there exists only one public key.
Therefore the decryption oracle will always decrypt with the secret key that corresponds to the public key given to the attacker. It does not matter how the $c_1$ in your question is computed, it can be computed using the real public key, a different public key or might even be random garbage. The decryption oracle doesn't care, it simply runs the decryption algorithm with the secret key produced earlier in the security game and the input provided by the attacker.
Whether this results in a valid decryption or not depends on the encryption scheme and is not part of the security definition.


The difference between these 4 breaking Cipher techniques? I'm trying to understand the difference between the following and what they actually mean :

Known plaintext attack
Known ciphertext attack
Chosen ciphertext attack
Chosen plaintext attack

Any clarification is much appreciated…

These aren't "attacks" in and of themselves, they are simply a way to classify attacks depending on how many assumptions they make. For instance, if an attack requires plaintext-ciphertext pairs to recover the key, but they don't have to be any particular pairs, that attack is categorized as a known-plaintext attack. However if another attack required the attacker to be able to give input plaintext and obtain the corresponding ciphertext, it would be a chosen-plaintext attack.

To summarize, from weakest to strongest in terms of assumptions made and data requirements:

Known Ciphertext Attack

The attacker is given some ciphertext, but does not know (or does not know exactly) what the plaintext corresponding to this ciphertext is. As with the previous type of attack, he does not get to choose what ciphertexts he obtains, and cannot produce more.

This is the weakest type of attack, as the attacker has essentially nothing to work with except a few ciphertexts obtained from eavesdropping or other. As such, it is typically the hardest to design, but the easiest to implement/carry out.

Example:

Eve steals a bunch of ciphertexts from Alice's handbag, but has no idea what they mean.

Known Plaintext Attack

The attacker is given some plaintext-ciphertext pairs which he didn't choose (say, obtained from an encrypted conversation between two people - he knows what the conversation is about, but he didn't get to choose what was said). The attacker cannot produce more plaintext-ciphertext pairs, he has to obtain them from whoever has the key, for instance by eavesdropping again.

Example:

Eve overhears an encrypted communication from Bob to Alice, and later observes them meeting at Baker Street - Eve can now guess that the communication contained the word "baker street" somewhere, a form of known plaintext attack.

Chosen Plaintext Attack

The attacker is able to select any plaintext and obtain the corresponding ciphertext through that which is known as an encryption oracle, which is a sort of black box that produces the corresponding ciphertext given any plaintext under the sought-after key, but does not reveal the key itself (i.e. you can't crack it open and just grab the key).

Note: there are two types of chosen plaintext attacks. Either the attacker can only submit a set of plaintexts once to the oracle, after which he can no longer use it (batch chosen-plaintext attack), or he can use the oracle interactively, able to select new plaintext based on what the oracle tells him (adaptive chosen-plaintext attacks).

Example:

A poorly designed file storage system uses the same key to encrypt everyone's files, and lets anyone see anyone's files (in encrypted form). Eve knows Bob uses the service, she registers as well and starts encrypting arbitrary files (which she can choose) and looks at the resulting ciphertext. From this she obtains the service's encryption key, and decrypts Bob's stuff.

Chosen Ciphertext Attack

This is essentially the opposite of the previous attack, the attacker can choose any ciphertext he wants and obtain the corresponding plaintext using a decryption oracle. It is however a stronger attack model than a chosen plaintext attack, and the strongest of all four here (but there are even stronger models outside the scope of your question, such as related-key attacks).

Example:

Eve breaks into Bob's house while he is sleeping, and replaces the ciphertext he was going to send to Alice tomorrow with a new one of her choosing. She then eavesdrops on their communications (encrypted or not) the next day to try and work out what Alice read when she decrypted the fake ciphertext (variants of this involve Eve not just creating a new ciphertext, but modifying the existing one slightly).

Encryption and decryption oracles are generally concretized as weaknesses in an interactive protocol which allow an attacker to attempt to impersonate a legitimate user and obtain information from the other party (but there are many other situations that may cause the attacker to have access to an oracle, of course). They aren't actually "oracles" that helpfully assist the attacker, that is only a mathematical abstraction.
As per Kerckhoffs's principle, the attacker is assumed to always know the internals of the cipher used, in addition to whatever plaintext or ciphertext he may have access to.
Note that some of the attack types above are mutually exclusive (for instance, an attack can't be both chosen-plaintext and known-plaintext).
Chosen plaintext/ciphertext attacks are somewhat exclusive to the modern ages of cryptography. In the past, such oracles were difficult to obtain, as physical communication between parties was not easy. However, they were not completely unknown, for instance, during WW2, Allied cryptographers routinely carried out maneuvers to tempt the Germans into sending specific messages encrypted with the Enigma (as an oversimplified example, by destroying an enemy ship, they could then be reasonably sure subsequent transmissions would contain the words "ship" and "destroyed" - a form of chosen plaintext attack, just not with an entirely reliable oracle).


What are the smallest possible RSA private and public keys? I'm trying to understand what the smallest possible RSA public and private keys are.
When using $p = 2, q = 3$, the encryption function doesn't encrypt. So I have to shift one prime to get $p = 3, q = 3$ and then the private key is $(9, 3)$ and the public key is also $(9, 3)$. I know that it is trivial to factor the product of two equal primes and it is bad to have the identical private and public key. However is it the lowest (feasible) RSA key pair or am I missing something here?

Per the definition of RSA in PKCS#1v2.2

In a valid RSA private key, the RSA modulus $n$ is the product of $u$ distinct odd primes $r_i$, $i=1$, $2$, …, $u$, where $u\ge2$.

That makes $n=3\cdot5=15$ the smallest public modulus.

and the RSA public exponent $e$ is an integer between $3$ and $n–1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

That makes $e=3$ the smallest public exponent. $(n,e)=(15,3)$ happens to be a valid public key, since $\lambda(15)=4$ and $\operatorname{GCD}(3,4)=1$.

The RSA private exponent $d$ is a positive integer less than $n$ satisfying $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

That makes $d=1$ the smallest private exponent. It corresponds e.g. to $(n,e)=(15,5)$. Encryption (and decryption) with that key is identity, but there is no worded prescription against that.

If we prohibit $d=1$, then $d=3$ becomes the smallest private exponent, matching $(n,e)=(15,3)$. More generally, different definitions of RSA yield different lower limits. Allowing $u=1$, $e=1$, and removing the prescription that $r_i$ is odd, makes $(n,e,d)=(2,1,1)$ acceptable. For FIPS 186-4, the smallest $n$ is 1024-bit, likelyA $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; the smallest $e$ is $65537\,$; and the smallest $d$ isB $2^{512}+1$.

A: Under the plausible assumption that each of $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$,  $\lfloor2^{1023/2}\rfloor+2^{412}+430$ and $\lfloor2^{1023/2}\rfloor+2^{412}+432$ has a prime factor at least $2^{100}$, which I did not check.
B: Some valid matching public key $(n,e)$ exists with high likelihood. It's a mildly interesting problem to exhibit one.


RSA problem if i choose two specific small prime numbers? I know that rsa normally is made to make it with big integers, but i trying to make the algorithm myself (with the help of wikipedia) and I´m making it with small numbers to track the problems easily.

The problem is that sometimes the decryption of the crypted message is wrong!
Exactly when I choose p=11 and q=5, the rest goes like this:

n=55
euler(n)=40 = (p-1)(q-1)
e=13
d=37

the crypted message (using message=65) is:

c=10

and using the chinese reminder theorem (wikipedia´s advise):

Dp=7
Dq=1
Qinv=9
m1=10
m2=0
h=2

and the decrypted message is:

message=10 !!!!!

It´s a problem of the choosen prime numbers? I think that the rest I made it fine, I also check it with rsa calculator:
https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html

I know also that to choose d and e there are more options, but the choosen ones they would be fine too. Maybe there is some other condition that is not in the wikipedia?

Actually, that's an expected result since $65 \equiv 10 \pmod{55}$.

You should choose $m < n$ to avoid this problem.


Why doesn't the ability to sample a single random bit imply the construction of a random oracle? I'm trying to understand exactly how the random oracle model differs from the standard model. In many proofs & applications there are some assumptions that some randomness is sampled (i.e. a bit $b \leftarrow\{0,1\}$).

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $H:\{0,1\}^m \rightarrow \{0,1\}^n$. Just sample $n$ bits for the output, and keep a log so that all future queries are consistent.

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $H:\{0,1\}^m \rightarrow \{0,1\}^n$. Just sample $n$ bits for the output, and keep a log so that all future queries are consistent.

Sure.  You could design a signature scheme where there is a central party—a gnome sitting in a standard box flipping coins—and everyone on the planet has a telephone line directly to the gnome that cannot be intercepted so that everyone gets the same values from the gnome.  That's not a particularly practical way to design a cryptosystem—we might like to be able to sign and verify messages offline, for example—but more importantly, it's not really what the random oracle model is about.

The random oracle model is not a just model for hash functions, but a model for adversaries.  Let's take an example: in the signature game EUF-CMA—existential unforgeability under chosen-message attack—an adversary $A$ is by definition a random algorithm with access to a signing oracle and a public key: $A(S, \mathit{pk})$.  The adversary wins if they can find any $(m, \sigma)$ pair that passes signature verification for any message $m$ they did not pass to the signing oracle $S$.  This is sometimes called the ‘standard model’.

In the random oracle model, we consider a family of signature schemes indexed by a uniform random choice of function $H$.  To make it clear that it depends on the hash function, we might label the signing oracle $S_H$.  For example, in RSA-FDH signature, a public key is a large integer $n$ and a signature on a message $m$ is an integer $\sigma$ such that $$\sigma^3 \equiv H(m) \pmod n.$$  The signing oracle for a legitimate user is typically defined by $$S_H(m) := H(m)^d \pmod n,$$ where the secret exponent $d$ solves $3d \equiv 1 \pmod{\lambda(n)}$.  Then, in the random oracle model, the adversary gets not just a signing oracle and public key as in $A(S, n)$ in the ‘standard model’, but also the hash oracle as in $A(H, S_H, n)$.

A ROM theorem is a statement of the following form:

If there is a random algorithm $A(H, S_H, n)$ which, when $H$ is uniformly distributed, returns a forgery with high probability, then there is an algorithm $A'(y, n)$ which, when $y$ is uniformly distributed, returns a cube root of $y$ modulo $n$ with high probability.

The proof of the theorem is a definition of the algorithm $A'$, which constructs a hash oracle and signing oracle that have the correct distribution to fool the forger, but additionally do enough bookkeeping to extract a cube root out of whatever computations the forger does—without using the secret knowledge of $d$ that the legitimate user would have.

Obviously, internally the random algorithm $A'$ will involve flipping coins just like you described, to implement the hash oracle and the signing oracle.  See my earlier ROM answer for details of the proof, and for more background, history, and literature references; see also the standard Bellare & Rogaway paper for the original proof of the RSA-FDH theorem in particular.

In other words, the random oracle model is an assumption about how adversaries are structured.  Rather than using the somewhat confusing term ‘random oracle model’, some authors prefer to say that the theorem quoted above is simply a theorem about $H$-generic adversaries, meaning adversaries that are defined generically in terms of an arbitrary hash function rather than adversaries that exploit details of a particular hash function like collisions in MD5.

MD5-specific forgers have been exhibited, of course—for example, they figured prominently in an international incident of industrial sabotage by the United States and Israel against Iran—but they do not contradict this theorem, because such forgers only work with extremely low probability when $H$ is uniformly distributed.  In other words, if an RSA-FDH signature scheme instantiated with MD5 goes bad, it's not because the fancy math of RSA-FDH went bad—rather, it's because MD5 went bad, and there's a good chance that using SHAKE128 instead will be fine.


How do I check if the output of my CFB TEA encryption algorithm is correct? I have an assignment question regarding the TEA cipher in CFB mode. After much difficulty and research, I managed to produce an 8-bit TEA / CFB encryption algorithm. My input is supposed to be a number in string format; for example; "12345678".

This is the result of the encryption

However, i do not have any way to check if the encrypted message is indeed correct.

I do understand a way to find out if it is correct is by programming a CFB mode decryption. Unfortunately, THE decryption of the ciphertext I generated is different from the initial plaintext.

Hence, I'm a little confused on whether is it my encryption that is incorrect or is my decryption that is incorrect.

Is there any way to verify if the encrypted message output is correct? Or is the CFB mode decryption method the only way to verify?

No, there are of course other methods of verifying your implementation.

Note that there are a few separate steps that can be distinguished:

the TEA block cipher;
the CFB mode (using the right number of bits to forward);
The encoding of the message and ciphertext.

First, test your block cipher (without CFB mode of operation) against any available test vectors. There seem to be a few available.

Second, test your CFB mode of encryption with a well known block cipher, e.g. DES, Triple-DES or blowfish (all come with 64 bit block size, just like TEA). You will need to establish key, IV and number of bits that are forwarded within CFB mode encryption (CFB-8 or CFB-64?).

Thirdly, test your encoding / decoding. You should treat the output of TEA as binary, not as text. For the input message you need a well described, canonical way of creating a message using numbers. Of course this encoding / decoding must be reversible. The codec should be tested separately first.

Finally, try and see if the combination of all three works as expected. If you cannot find text vectors directly then try and use a different implementation (and test that against text vectors first).

You could also use a third party implementation to create intermediate values, so you can verify the correctness of your implementation.

Here's a test vector created using Bouncy Castle (Java, v1.57) and, of course, hexadecimals to represent the bytes:

TEA in CFB-8 mode
K : 2c1003d83c3c3707a92a10f45a3bd72f
IV: 681574192889be9d
M : 3132333435363738
C : d2751754c6699453

This is the kind of representation you need to test. Note that the input message M consists of the ASCII encoding of the string "12345678". The 128 bit key and full 64 bit IV have been randomized.


Additive inverse for elliptic curve addition in finite field in jacobian coordinates I wrote a solidity smart contract for elliptic curve point addition in Jacobian coordinates.

Jacobian coordinates: [X,Y,Z]
Affine representation: [x,y]=[X/Z^2, Y/Z^3]

I used the following formulas: Link. My code seems to work fine however my questions are:

What is the additive inverse in Jacobian coordinates? Is it the point at infinity and the result therefore: P-P=[0,1,0]?
My elliptic curve multiplication function seems to have an error, any idea? I think I need to set the start value of R to "additive zero for points".

// function for elliptic curve multiplication in jacobian coordinates using Double-and-add method
function ecmul(uint256[3] P, uint256 d) constant returns (uint256[3] R) {

  R[0]=0;
  R[1]=0;
  R[2]=0;

  //return (0,0) if d=0 or (x1,y1)=(0,0)
  if (d == 0 || ((P[0]==0) && (P[1]==0)) ) {
    return (R);
  }
  uint256[3] memory T;
  T[0]=P[0]; //x-coordinate temp
  T[1]=P[1]; //y-coordinate temp
  T[2]=P[2]; //z-coordiante temp

  while (d != 0) {
    if ((d & 1) == 1) {  //if last bit is 1 add T to result
      R = ecadd(R,T);
    }
    T = ecdouble(T);    //double temporary coordinates
    d=d/2;              //"cut off" last bit
  }

  return R;
}

The projective form of Weierstrass equation of an elliptic curve is obtained by replacing $x$ by $X/Z^c$ and $y$ by $Y/Z^d$. If $c=d=1$ then we have standard projective coordinates. In this state, point at infinity is $(0:1:0)$. But in Jacobian coordinates($c=2$ and $d=3$), point at infinity is $(1:1:0)$.

As poncho said in comments, The additive inverse of the point $(X:Y:Z)$ is  $(X:-Y:Z)$ .


Tests on /dev/urandom entropy can be considered useful or not? i want to test the entropy of my seed generator: in my case is /dev/urandom.
I've read that this operation is non useful because it is the result of CSPRNG (normally not accessible).

But what i obtain from urandom is the seed for my RBG algorithm and than it is the real seed for me.

Do you think the test can be useful or not? Do you have any suggestion on how it should be performed?

Bear in mind that entropy is measured against a source using a model. It is unlikely you will find any model or attack against /dev/urandom that worked purely by analysing its output - from that perspective it will have "perfect" entropy by any realistic measure. However, so would Mersenne Twister unless you knew how to build a model that extracted its state . . . in which case you could reduce that to zero entropy after 624 measurements.

In short, measuring "entropy" of any RNG with a generic model is unlikely to show you anything. If you don't take care, even very bad RNGs will pass tests such as compressibility or naive checks for patterns.

There are tools that allow you to check that a source is statistically random in various ways. I could suggest Dieharder as it provides a command-line interface which is easy to connect via a *nix pipe. This will run a variety of simulations and pattern-detection algorithms against a source of alleged random bytes.

A test against /dev/urandom should look like this:

cat /dev/urandom | dieharder -g 200 -a

. . . and may take a few hours to complete, since the tests consume large amounts of source data.

Caveats:

Proving something is "random" is not easy. At best you get a probability of getting the same result from a theoretical truly random source. If you run hundreds of tests (like Dieharder does), then some will probably end up reporting a low $p$ value - e.g. 0.01 or less. This is not necessarily bad. RNGs that really fail Dieharder tend to do so very dramatically with $p < 0.000001$ in multiple related tests.
If you find that a source is statistically random, that does not mean it is secure, just that it has demonstrated one desirable property of a secure system.


Can "Approximate Hashing" work in a Proof-of-Work context? Here is a draft of an article claimed to soon appear in a peer-reviewed conference: Matthew Vilim, Uenry Duwe, Rakesh Kumar, Approximate Bitcoin Mining.

It is proposed to simplifying a SHA-256 engine (used in a Proof-of-Work context) in some way, at the expense of quite always having a correct result; and concluded that the ASIC area saved allows to implement significantly more (or/and faster or/and more power efficient) SHA-256 engines on the same area, with the potential of increasing the expected work demonstrated (translating to profit obtained by bitcoin mining gear using the design by 30% overall).

Increasing work demonstrated implies that the rate of correct SHA-256 produced increases at least as much (in a bitcoin context: twice as much, since an incorrect SHA-256 in the two chained SHA-256 characterizing a valid bitcoin will make it rejected with overwhelming certainty, yielding no profit; and odds that a SHA-256 input yields an incorrect result will be largely independent of whether it is involved with a valid bitcoin).

However, I find it hard to believe that the rate of correct SHA-256 obtained does not fall down steeply when we remove any sizable portion of whatever part of a competent ASIC design computing SHA-256 for Proof-of-Work (including the carry-look-ahead logic that is considered as the target of the area reduction).

Any well-informed opinion+explanation?

In the paper the following remark is probably most important:

  For example, observing the frequency-error
  characteristics of Figure 4, the hashing cores corresponding
  to both approximate adders, $\operatorname{GDA}_{(1,4)}$ and $\operatorname{KSA}_{16}$, have negligible error rates at nominal frequency. Also, their nominal
  operating frequencies are higher than their non-approximate
  counterparts, $\operatorname{CLA}$ and $\operatorname{KSA}_{32}$ respectively.

It is further also said that $\operatorname{KSA}_8$ doesn't work because the error rate is so high that the SHA-256 hash is (almost) 100% certain to be wrong.

So it is clear that the double SHA-256 hash still has a large success rate, to be precise the error rate of the "core hash function" is
$7.27 × 10^{−3}$ for $\operatorname{GDA}_{(1,4)}$ and $8.79 × 10^{−2}$ for $\operatorname{KSA}_{16}$. Apparently that is small enough an error rate to be good enough compared to the (estimated / calculated) increased speed and reduced die size. This is not that strange, you should just be able to multiply the success rate of the double hash $(1-\varepsilon)^2$ with the speed increase.

Note that incorrect positive results results are not much of an issue within BitCoin; if you find a hash you can very easily verify the result (a correct hash is currently found every 10 minutes, and an approximate hasher is unlikely to change that frequency).

Obviously there is also the problem with missed, correct hashes. This means that - apart from the higher speed mining - there there is also a small amount of blocks missed that should contain a bitcoin. This should however not matter much; it's not known in advance if a block contains a coin and the amount of blocks missed will be minimal.


Is DSA vulnerable if verifier doesn't check r' > 0? If a DSA implementation neglects to check $r' > 0$ when verifying signatures, what are the consequences? Creating a forged $s$ would seem to require solving for $k$

$g^k mod\ p = nq$

which is still a hard problem?

Assume that all other range checks for parameters are being carried out (particularly $r' < q$)

Let's write down naming conventions explicitly:

We work modulo prime $p$. There is a smaller prime $q$ that divides $p-1$; we write $p = 1 + qn$ for some integer $n$. Traditionally, the sizes of $p$ and $q$ would have been 1024 and 160 bits, respectively; nowadays, we would rather use 2048 and 256 bits.
$g$ is an integer modulo $p$ of order $q$; i.e. $1 < g < p$, and $g^q = 1 \pmod p$.
Private key is some non-zero integer $x$ modulo $q$.
Public key is: $y = g^x \pmod p$
Normal signature generation is:

Generate a random non-zero $k$ modulo $q$.
Compute $r = g^k \pmod p \pmod q$ (we compute the exponentiation modulo $p$, and the result, which is in the $0$ to $p-1$ range, is further reduced modulo $q$). At that point the signer is supposed to check that $r \neq 0$; if that very improbable case shows up, then he should start again with a new random $k$.
Compute $s = (h+xr)/k \pmod q$ where $h$ is the hash of the message, suitably truncated and reduced modulo $q$.

Normal signature verification is:

Verify that $r$ and $s$ are in the $0$ to $q-1$ range.
Verify that $r \neq 0$.
Compute: $w = 1/s \pmod q$
Compute: $r' = g^{wh} y^{wr} \pmod p \pmod q$
Signature is considered valid if and only if $r = r'$.

The question is then: what if the verifier does not check that $r\neq 0$ ? In other terms, if a signature such that $r = 0$ is deemed acceptable, then does this allow attackers to forge signatures?

The attacker succeeds if he can show values $(r, s)$ that fulfill the equation:

$$  g^{wh} y^{wr} \pmod p \pmod q = r $$

where $h$ is a given (hash function output). If $r = 0$, then this simplifies to:

$$ g^{wh} = 0 \pmod p \pmod q $$

If there is an integer $u$ modulo $q$ such that $g^u = 0 \pmod p \pmod q$, and the attacker can find it, then a forgery is easily computed by setting $s = u/h \pmod q$. This can allow forgery for any message, and, interestingly, for any public key $y$ that uses these DSA parameters, since $y$ does not appear at all in the equation.

Now the attacker's problem is finding that value $u$, if it exists. Now comes the hand-wavy part: this problems seems difficult, for the following reason: there are very few solutions.

Namely, $g$ generates a subgroup of size $q$, and there are about $p/q$ values modulo $p$ which are also a multiple of $q$. So the possible solutions $u$ are in the intersection of a set of size $q$ (the subgroup) and a set of size $p/q$ (the multiples of $q$), both sets being subsets of a set of size $p$ (the integers modulo $q$). If both subsets were generated randomly, then the probability of having no common element would be about $((q-1)/q)^q$, which converges to $e^{-1} \approx 0.3679$ when $q$ is large. In other words, in about 37% of the cases, there will be no solution at all, i.e. there would be no signature with $r = 0$ that the verifier would accept. And when there is a solution, there will usually be only one or two.

Thus, the attacker's job is about finding a discrete logarithm $u$, in base $g$, for a single target value. This is exactly the discrete logarithm problem and we assume it to be hard modulo $p$ (otherwise, why would you use DSA at all?). Note that this would hold even if the attacker knows exactly what multiple of $q$ he should target; not knowing that value makes the task only harder for him.

Now, of course, the two subsets are not generated randomly. I made some measures with small values. For instance, with $p = 1993$ and $q = 89$, then none of the elements of the subgroup of order $q$ is a multiple of $q$; however, with $p = 1553$ and $q = 97$, using $g = 310$, then $g^6 \pmod p = 776$, which is a multiple of $97$, and $g^{18} \pmod p = 194$, which is also a multiple of $97$.

Generating all possible DSA parameters such that $200 \leq q \leq 500$ and $100000 \leq p \leq 200000$, I find 1218 sets of DSA parameters; for 442 of them (36.3%), there is no solution; for 438 (36.0%), there is exactly one solution; for 231 (19.0%) there are exactly two solutions; and so on. This is compatible with the analysis above: solutions are rare, so finding a solution should be as hard as solving discrete logarithm generically.

(Unless there's some magical math that allows easily finding a solution in that specific case. Sometimes the World does that, just to spite me.)


Using RSA keys for Broadcast Encryption? What is the best way of using both broadcast encryption and RSA private keys? I'm particularly interested in Broadcast Encryption as implemented by BGW 1, but I guess that the question stands for any broadcast encryption system.

My confusion comes from the fact that the initial phase of Broadcast Encryption takes in the number of users and creates one global Public Key and a Private Key for each user. But suppose that the users in the system already had RSA private keys assigned. Is there a way to mitigate the fact that we need to maintain two private keys per each user (one from RSA and one from Broadcast Encryption) ?

1 Boneh, Dan, Craig Gentry, and Brent Waters. "Collusion resistant broadcast encryption with short ciphertexts and private keys." Annual International Cryptology Conference. Springer Berlin Heidelberg, 2005.

The Broadcast encryption scheme you link to uses elliptic curve groups based on the bilinear map (bilinear pairing). RSA is not elliptic curve based.

  Is there a way to mitigate the fact that we need to maintain two private keys per each user (one from RSA and one from Broadcast Encryption) ?

This is not trivially possible. You would have to devise a scheme that combines those two primitives.

The only scheme I know of that combines RSA with bilinear pairing is Comparison-based encryption for fine-grained access control in clouds by Zhu et al. (DOI: 10.1145/2133601.2133614)

You might want to check that to see if you can salvage some of that, but I doubt that you will be successful.

Why integrating them is not a good idea in your case:

If your users already have their RSA private keys, then those RSA private keys are not linked in mathematically aside from following the same key generation process. In order to get the ciphertext size improvement of broadcast encryption (BE), you'd need to find some hidden property between all of the RSA private keys just by looking at the RSA public keys of your users. For that, you will either have to break RSA (not an easy feat) or you need to ask the users for their RSA private keys. If you ask for RSA private keys, you might as well just replace them with the BE private keys and skip the integration.


Computational Complexity Of Breaking Information Theoretic Security Wikipedia mentions that Shamir's secret sharing(SSS) for example, has information theoretic security. While I understand the concept that the adversary would just not have enough information to break the security, it must also correspond to some computatioal complexity class, shouldn't it? Let's say I'm an adversary and am presented with an instance of SSS. I have unlimited computational powers. Would I find it at least as hard as the Halting problem? Is it easier than that? Which class can be assigned to breaking such information theoretically secure protocols?

Here's an simpler but analogous problem that may illustrate what's going on:

Given that $X=Y+Z$ and $Y=5$, compute $X$.

The problem isn't that the answer is difficult to compute, the problem is that there isn't enough information there to give you any idea (any information about) what the answer is. That's what's meant by information-theoretic security.
(Note: what I've given above isn't actually an example of SSS, and if you actually try to apply statistical information theory to it, you'll run into trouble because the integers are infinite. If you're really worried about the latter issue, assume we're doing arithmetic modulo some integer $>5$)


How to check whether the permutation is random or not Imagine that my friend gives me the permutation $\pi$. He pretends that the permutation was generated completely random.

I'm suspicious and worried, because the permutation (for instance) looks like: $\pi(x) = ax + b \pmod n$ for some $a$, $b$. My friend said to me that it happens by chance.

Of course it is not possible for me to actually prove that permutation is not random, because we always can generate this one by chance.

Is there any strategy using which I can rigorously state (as a mathematical statement) that this event is very unplausible?

I can try to say something like : well, there is a structure, and a chance that random permutation will have this structure is really small. But the structure can be more tricky (for example, k-round Feistel network over some group with some round functions or the like). And my friend is telling me: well you can always invent some tricky formula and get every my permutation. But this does not indicate that the permutation is not random.

So the question is: if I found some "hidden" structure in "random" object, does it indicate that the object is very unlikely to be random or I can always find structure in every object that friend gives to me? How this "suspiciousness" can be quantified in the rigorous mathematical sense?

There are at most $n \cdot (n - 1)$ permutations of $\mathbb Z/n\mathbb Z$ of the form $x \mapsto ax + b$: if $n$ is prime, there are $n - 1$ choices for $a$ and $n$ choices for $b$ under which this is a permutation.  There are $n!$ permutations of $\mathbb Z/n\mathbb Z$ altogether.  So the probability that a uniform random permutation has this form is negligible if $n$ is even modest in size—the probability is at most $n \cdot (n - 1)/n! = 1/(n - 2)!$, which gets very small very quickly as $n$ grows.  For example, for $n = 64$, this probability is already less than $1/2^{256}$, which, in cryptographic terms, is not-gonna-happen squared.

You can confidently verify whether it has this form given oracle access to the permutation simply by querying it on two different inputs and solving for $a$ and $b$, and then checking it on a third point, and a fourth point, etc., to see if they match.

Exercise: Compute the false alarm rate of this test for a uniform random permutation as a function of the number of confirmation points.  The statistical power of the test under the alternative hypothesis of the form $x \mapsto ax + b$, of course, is the maximum possible: 1.
You can confidently say your friend is not being entirely forthcoming about how they chose the permutation if it has this form (e.g., it's an 8-bit permutation and you can verify all 256 outputs) but they claim they chose it uniformly at random.

For an 8-bit permutation, the probability of falsely accusing your friend in the event they actually did choose the permutation uniformly at random—the false alarm rate, or ‘statistical significance’—is below $1/2^{256}$, the equivalent of ‘$p < .0000…00001$’ (77 zeros).

However, that's only for this particular test, if you devised the test without knowledge of the permutation.  If your friend gives you a permutation and based on the permutation you devise a test that it fails, that may not mean anything—for any particular choice of permutation, there are many tests with low false alarm rates that it will fail.  And if you string many tests together, so that any one of them will raise an alarm, then the false alarm rate rises—a standard consequence of ‘$p$-value hacking’ or the ‘garden of forking paths’.

This question is similar to the issues surrounding the hash function Стрибог (Streebog), from the Russian federal government standard ГОСТ Р 34.11-2012 (also RFC 6986), and the block cipher Кузнечик (Kuznyechik), from ГОСТ Р 34.12-2015 (English; also RFC 7801).

In 2015, Alex Biryukov, Léo Perrin, and Aleksei Udovenko discovered a remarkable structure in the S-box—a permutation of 8-bit strings which the Streebog designers maintain was chosen at random by rejection sampling on uniform random S-boxes (archived).

When Perrin et al. identified the structure, they reasoned that the designers' story is implausible because there are $256! \approx \sqrt{2\pi\,256\,} (256/e)^{256} \approx 2^{1684}$ possible S-boxes, of which only about $2^{82}$ admit a neat concise description with the special structure.

‘But,’ you object, ‘knowing my permutation, you could invent any tiny class of permutations containing my permutation even if I really did choose it uniformly at random.  Then you could use the low probability of your class to claim that I must have chosen my permutation from that class intentionally, rather than guessing it by luck!  That doesn't mean anything!’  (This is essentially the argument made by the designers to claim that they are not lying spooks, according to Léo Perrin, as recently as a couple of weeks ago at an ISO standardization meeting.)

So Perrin put it to codegolf.SE, whose participants came up with various short descriptions of the permutation including a 78-byte, or 624-bit, AMD64 instruction sequence.

A code-golfing exercise is interesting not so much because a program can be invented that is shorter (for example, a 1-bit program for a machine that either computes the S-box if the program is 0, or returns zero if the program is 1), but because the AMD64 instruction set was presumably designed without knowledge of the chosen S-box—and if the Streebog designers really did sample from permutations uniformly at random to choose the S-box, the probability of getting one that admits a 78-byte/624-bit description in the AMD64 instruction set is at most $2^{624}\!/2^{1684} = 1/2^{1060}$.  Of course, the Streebog designers had some criteria for rejection sampling, but even if they went through a quintillion candidates this way (short scale, about $2^{60}$), the probability would remain less than $1/2^{1000}$.

Another way to look at it is:

Imagine writing down a sequence of all ${\approx}2^{1684}$ 8-bit permutations, labeling them $1,$ $2,$ $\dotsc,$ $2^{1684} - \mathit{whatever}$.  It doesn't matter what order you put them in; you can put them in any order you want, as long as you do it without seeing into the future of what I'm about to do.

If I then pick a permutation uniformly at random, there's a 1/2 chance it'll be in the first half of your sequence.  There's a 1/4 chance it'll be in the first half of the first half—that is, the first quarter—of your sequence.  More generally, there's a $1/2^n$ chance it'll be in the first half of the first half of the first half…of the first half ($n$ times)—same odds as flipping a coin $n$ times and having it come up heads every time.  If I wanted to find a permutation in that region by trying them uniformly at random until one works, the expected number of permutations I'd have to try is about $2^n$.
Now imagine writing out all byte strings: (empty), 0x00, 0x01, 0x02, …, 0xff, 0x00 0x00, 0x01 0x00, 0x02 0x00, …, 0x00 0x01, 0x01 0x01, 0x02 0x01, and so on.  Some of these are valid AMD64 instruction sequences.  Some of the valid AMD64 instruction sequences implement permutations (say, permuting the value of AL, ignoring all other architectural state).

You certainly need at least 211 bytes to cover all of the permutations this way, because with only 210 bytes = 1680 bits, there are more 8-bit permutations than there are sequences of 210 bytes.  You almost certainly need more than 211 bytes, too, because most AMD64 instructions sequences do not compute permutations—but you don't need much more than 256 bytes, because you could use a 256-byte table of all inputs and outputs in ROM and then a MOV instruction or two to use it.

So, you have now laid out a sequence of all 8-bit permutations by enumerating AMD64 instruction sequences.  Somehow, by allegedly doing rejection sampling on uniform random choices of 8-bit permutations, the designers found one that lies in the first half of the first half of the first half…of the first half of this sequence, iterated over a thousand times, an event with probability less than $1/2^{1000}$—even if they rejected a quintillion candidates first.

If you wrote out any sequence of a thousand coin toss outcomes—THTTHHHTHT…—and then watched a gambler flip a coin a thousand times coming up with exactly your sequence while looking at it, would you believe that they were doing fair coin tosses, or would you begin to suspect they might be pretty good at flipping coins to come up the way they want?

Of course, in principle, this could still be a fluke: By shopping around to different languages in the garden of forking paths, we could maybe find a language in which this permutation by chance happens to turn up early in the sequence…by shopping through about $2^{990}$ different programming languages to raise the probability of a false alarm from $2^{-1000}$ to a mere one-in-a-thousand $2^{-10}$.  But (a) it is not plausible that codegolf.SE tried out $2^{990}$ different programming languages, and (b) besides AMD64 instructions, there are also now descriptions of the same S-box in many languages that all clock in at well under 200 bytes, including C, C#, JavaScript, Rust, and Python.

There's an alternative hypothesis: Like a gambler who can make a coin come up the way they want (it's actually quite easy!), the Streebog designers may have used a method of generating the S-box that enabled compact, efficient implementation which they just aren't telling anyone about.  The outcome of such a method—even if randomized—would be much more likely to have many short descriptions in existing programming languages.  In a Bayesian analysis, whatever prior odds ratio we assigned to the hypotheses $\text{structured}$ and $\text{uniform random}$ (i.e., the relative plausibility of the two hypotheses a priori), we can write the posterior odds ratio by Bayes' rule in terms of the prior odds ratio and the likelihood ratio as:

\begin{multline*}
  \frac{\Pr[\text{structured} \mid \text{78-byte code golf}]}
       {\Pr[\text{uniform random} \mid \text{78-byte code golf}]} \\
   = \frac{\Pr[\text{structured}]}{\Pr[\text{uniform random}]}
     \cdot
     \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]}
          {\Pr[\text{78-byte code golf} \mid \text{uniform random}]}.
\end{multline*}

It is obviously hard to quantify what $\Pr[\text{78-byte code golf} \mid \text{structured}]$ is without a clearer idea of what structures the Streebog designers might have considered, but let's say that there's about a one-in-a-googol ($10^{100} \approx 2^{332}$) chance that there's a 78-byte code golf solution in a well-known widely-used programming language for the method the Streebog designers used.  In that case, we might measure the magnitude of code golf as evidence for the structured hypothesis over the uniform random hypothesis—the likelihood ratio, which is the ratio of the posterior odds ratio to the prior odds ratio, measured in decibels—as

\begin{multline*}
  10 \log_{10}
    \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]}
         {\Pr[\text{78-byte code golf} \mid \text{uniform random}]} \\
  \leq 10 \log_{10} \frac{2^{-332}}{2^{-1000}}
  = 10 \log_{10} 2^{790}
  \approx 2000\,\mathrm{dB}.
\end{multline*}

To put this number in perspective, the magnitude of evidence we demand in cryptography before accepting a message in typical message authentication code rather than rejecting it as a forgery is over $300\,\mathrm{dB}$—and remember that decibels are a logarithmic scale.  (For more on measuring weight of evidence between two hypotheses in decibels, see Jaynes's book, particularly chapter 4.)

Of course, this is a very heuristic quantification of the evidence—it should really be taken mainly as an illustration of the Bayesian shape of reasoning.  There may also be other hypotheses which this analysis doesn't consider—for instance, perhaps the Streebog designers just used a particularly bad PRNG when allegedly performing a Fisher–Yates shuffle to generate the permutations, and didn't realize that they were exploring a subspace that has an interesting relation to the AMD64 instruction set.

Exercise: Hypothesize plausible PRNGs that the Streebog designers might have used, and extend this to a many-hypothesis Bayesian analysis.

For more on the background and references, see Léo Perrin's web site and the story so far at ASIACRYPT 2019.


What is the function of the secret key “r” in Poly1305? Poly1305-AES uses two per-connection keys $k$ (for AES) and $r$ (for Poly1305's compression function) and a per-message nonce n to execute.  I've read the original paper on the implementation, and I think I understand what it does, but not how it works.  In particular, if the security of the MAC is dominated by the security of $AES_k(n)$, why must $r$ be kept secret?

In other words: what are the security properties of $Poly1305_r(m)$ by itself, before adding $AES_k(n)$?

$Poly1305_{{r,s}}(m)$ is a one-time authenticator - it can be used to authenticate only a single message with any given key $(r,s)$ without violating the security guarantees (the violation is immediate - only two authenticated messages with the same key are required to create a forgery according to the nacl docs).

There are two 128 bit key values to this function (commonly combined into a single 256 bit key):

$r$ is the basis for the polynomial evaluation (in a specific format with some bits cleared)
$s$ is a key value that is added at the end to the result of the polynomial evaluation

Both of these values are part of the key - the specification requires that the key (including $r$) is unpredictable, and the size of the set $R$ from which $r$ is sampled does factor in the security proofs, so I would presume that exposing $r$ would compromise the security guarantee to some degree. Given the $2^{106}$ bound on that security, I would treat all parts of they key as secret.

$Poly1305{-}AES_{(r,k,n)}(m)$ extends $Poly1305$ into a general purpose MAC function - i.e. it can be used to authenticate many messages with a single key $(r,k)$ as long as the nonce $n$ is not repeated.
The extension is achieved by replacing the $s$ value in the one-time authenticator with the result of $AES_k(n)$, which produces an unpredictable value for each unique nonce.

The $AES$ part of the calculation can be replaced by another secure cipher - e.g. the nacl library uses $xsalsa20$ to encrypt the nonce, but other block ciphers like Serpent/Twofish etc. will work just as well.


Can specific Weierstrass curves be some benefit from Montgomery/Edward form? I have noticed that DBL/diffadd in Edward/Montgomery form almost double fast than Weierstrass form(EFD), and curve25519 is empressive high-performance.The transformation between these forms can be covered by two ModInvs at most(even two ModMults). So the scalar multiplication in specific elliptic curves like p256 or Secp256k1 could transfer to scalar_mult in Edward/Montgomery form.

Could these tranformation&AdditionChain&diffAdd be faster than the ordinary MADD&w-NAF&preCom methods?
Of course Curve25519 is designed for Montgomery form, but the wide spread Weierstrass curves also have well-designed prime number. To what extent will the curve parameters affected the performance of Montgomery/Edward scalar_mult?

Curves P-256 and Secp256k1 cannot be converted to Montgomery or Edwards forms because they are of prime order.

Let's take the example of Secp256k1 and try to convert it to a Montgomery curve:

A Montgomery curve $by^2=x^3+ax^2+x$ has a point of order 2. Such a point verifies $2P=\mathcal{O}$ or think of it equivalently $P=-P$ which means $(x,y)=(x,-y)$ so these points are on the $x$-axis. It is obvious then that the point $(0,0)$ on a Montgomery curve has order 2. Now given the secp256k1 curve $y^2\equiv x^3+7 \pmod p$ where $p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$, we are looking for points on the $x$-axis which means those that satisfy $x^3 \equiv -7 \pmod p$. There is no solution to this modular cubic equation.

In general curve P-256 and Secp256k1 cannot be converted to Montgomery form because they have a prime order ($\ne 2$) and thus they cannot have a point of order $2$ (otherwise $2$ would divide a prime number beacause of Lagrange's theorem).

The same reasoning works for Edwards curve $x^2+y^2=1+dx^2y^2$ because the point $(0,-1)$ has order $2$ and the points $(\pm 1, 0)$ have order $4$.


N way collision of hashes For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$ where $\log_2(T)$ is length of hash output. Then, what would be the number of queries requried to find an $n$-collision ($H(A_1) = H(A_2) = .....  = H(A_n)$).

is $T^{1-1/n}$

Proof:

Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. Since each one of these $n-1$ events happens with probability $1/|T|$, the probability that a particular set $N$ chosen from $M$ is a $n$-collision is $O(1/|T|^{n-1}))$.Using the union bound, the probability that some set $N$ is an $n$-collision is $O(m^n/|T|^{n-1})$ and since we want this probability to be close to 1, the bound on $m$ is $T^{1-1/n}$


Finding the IV of AES CBC (CTF) We have a python program that encrypts/decrypts plaintext given in hex to a cipher using AES CBC. We know that the IV is the same and is not going to change (it is stored in a file). How can we possibly find the IV, if found this will be the flag.

Request decryption for three blocks ( 2 is enough);
\begin{align}
P_1 =& Dec_k(C_1) \oplus IV\\
P_2 =& Dec_k(C_1) \oplus C_{0}\\
P_3 =& Dec_k(C_2) \oplus C_{1}\\
\end{align}
Now remove the first ciphertext, and request decryption;
\begin{align}
P'_2 =& Dec_k(C_1) \oplus IV\\
P_3 =& Dec_k(C_2) \oplus C_{1}\\
\end{align}
Now use the equations of $P_2$ and $P'_2$
$$\begin{align}
P_2 \oplus P'_2 &= Dec_k(C_1) \oplus C_{0} \oplus Dec_k(C_1) \oplus IV\\
& = C_{0} \oplus IV \\
P_2 \oplus P'_2 \oplus  C_{0} &= IV \\
\end{align}$$

In programmer aspect
defn CBCDecryptionOracle(c[]):
   return Dec(c[])

c = (c1,c2)

p1 = CBCDecryptionOracle(c)

d = c[0]

p2 = CBCDecryptionOracle(d)

print( p1[0] ^ p2 ^ c0)


Using nested signatures to trust public key of inner signatures I have a scenario where entity $A$ has an unauthentic copy of the public key $P_B$ of $B$ and an authentic copy of $P_C$ of $C$, trusted by both $A$ and $B$.

Now $A$ wants to establish trust in $P_B$.

Steps:

$B$ writes a message, signs it and sends it to $C$ : $$B \rightarrow C: M \| S_B(M)$$
$C$ is an intermediary entity and forwards the message to $A$ : $$C \rightarrow A : M \| S_B(M) \| S_C(M \| S_B(M))$$
$A$ then validates $S_C(S_B(M))$ and $S_B(M)$ successfully

Can $A$ now trust the authenticity of $P_B$ because the signature $S_B(M)$ was received in an authentic manner?

The practical example is DKIM in E-Mail infrastructure:

sender may sign her outgoing message (e.g. using PGP);
does not attach public key to not annoy non-PGP enabled receivers;
the message including the signature gets signed by the providers DKIM key;
the receiver gets a copy of the sender PK and wants to establish some trust beyond TOFU.

I think this depends heavily on the expectations and trust that A has with respect to C.  $A$ should be safe to now view $P_B$ as authentic provided that $A$ trusts that:

$C$ will only sign $B$'s message if it could successfully verify $S_B(M)$
$C$ would only use $P_B$ if it had previously obtained and verified the authenticity of $P_B$
$C$'s requirements for verifying the authenticity of $P_B$ are at least as strict as $A$'s

Note that this is essentially the same as with certificate authorities, where $P_x$ are X.509 certificates (e.g. $P_C$ is the root certificate for a CA, $C$).  $B$ can't expect to provide $P_B$ to everyone it expects to communicate with so instead it establishes trust with $C$ which then signs $P_B$.  When $A$ receives data from $B$, it would first receive $P_B || S_C(P_B)$ then $M || S_B(M)$.  $A$ then decides to trust $P_B$ on the grounds that $C$ would not have signed $P_B$ without first establishing it's authenticity. $A$ then, in turn, trusts that $M$, in fact, originated from $B$.

However, it's important to note the $A$ having authenticated $P_C$ is not sufficient.  Messages signed with $S_C$ may, in fact, be coming from $C$ but that does not mean that $C$ is fully trustworthy.  For $A$ to trust $C$'s trust of $P_B$, $A$ must also trust that $C$ is sufficiently cautious about establishing the authenticity of $P_B$.  Just as it would be extremely concerning if a trusted certificate authority were to start signing any certificate sent their way, $A$'s confidence in the authenticity of $M$ and $P_B$ must not be greater than $A$'s confidence in $C$'s process of establishing trust.

Similarly, if $C$ viewed its job simply as marking that it received and relayed the message, blindly signing the entire payload it received, $A$ would be mistakenly assuming an assurance not actually provided by $C$.

Long story short: $A$ can only trust $P_B$ if it trusts that $C$ is, and is sufficiently capable of, guaranteeing the authenticity of $P_B$.


what's the reason of the notational difference between statistical and computational indistinguishabilities? Statistical: $|\Pr[E_K(m_0)\in T]-\Pr[E_K(m_1)\in T]|\leq\epsilon$
Computational: $|\Pr[A(E_K(m_0))=1]-\Pr[A(E_K(m_1))=1]|\leq\epsilon(n)$
What is the $1$ doing there? Why isn't it $Pr[A(E_K(m_0))\in T]$? Is there something deep behind these different notations? or is it simply a convention of the PPT $A$ having a boolean as a return value?

You can define statistical security directly in terms of the statistical properties of different distributions. For example, you could define two distributions to be statistically close if their statistical distance is very small.
On the other hand, computational security is not precisely a statistical property of the given distributions.
As such, the two distributions under consideration may not be similar at all, in fact, they may be super different! but what matters for this notion of security is that it is not efficient to distinguish between the two.
To formalize this idea, you need to talk about distinguishers, which are algorithms that receive an input from one of the two distributions and try to guess which distribution it comes from.
This would the algorithm $A$ in your definition.
The intuition of the definition is that such algorithm will output some fixed value ($1$, in this case) with almost the same probability, independently from which of the two distributions the input is sampled from.


Is there a formula for calculating the inverse of a sum in modular arithmetic? Suppose there is a cyclic group $G$ of prime order $q$ of elements in $Z_p^*$ with a generator $g$ and a value $x \in Z_q$.

$h_1 = g^{x+1}$

$h_2 = g^{x}$

Is it possible to write $h_2^{((x+1)^{-1})}$ as some combination of $g$ and $h_1$?

$x+1$ is invertible in $Z_q$ only if $gcd(x+1,q)=1$, which means $ax+a = 1 \bmod q$ and $gcd(x,q)=1-a$, so $x$ is not invertable in $Z_q$. However, then it seems that  $h_2^{(x+1)^{-1}}$ can't be represented as combination of $g$ and $h_1$.

P.S. I'm trying to figure out whether verifier can distinguish real and fake proofs in this questions if verifier assumes that $x_{tr} = \hat{x}_{tr} +1$, computes $e$ for $\hat{h}$ but adjusts $r_{ch}$.

Is it possible to write $h_2^{((x+1)^{-1})}$ as some combination of $g$ and $h_1$?

No.  Computing $h_2^{((x+1)^{-1})}$ from $g, h_1$ is equivalent to the Computational Diffie Hellman (CDH) problem, which we believe is difficult for some groups.

Here is the proof in the forward direction (your problem is at least as hard); suppose that we had an Oracle that, given $g, h_1 = g^{x+1}$, was able to give us the value $h_2^{((x+1)^{-1})} = g^{x \cdot (x+1)^{-1}}$

First of all, let us set $y = x+1$, and rearrange the Oracle "given $g, g^y$, give us the value $g^{(y-1) \cdot y^{-1}} = g \cdot g^{-y^{-1}}$; with this Oracle, we can easily reconstruct the value $g^{y^{-1}}$.

It is well known that computing the value $g^{y^{-1}}$ given $g, g^y$ is equivalent to the CDH problem; given $h, h^a, h^b$ compute $h^{ab}$.  This is done by turning the inverse Oracle into a squaring Oracle (given $h, h^a$, compute $h^{a^2}$).  To do this, we set $g = h^a$ and $g^y = h = (h^a)^{a^{-1}}$; we give those two to our inverse Oracle, which returns us $(h^a)^a = h^{a^2}$

Once we have a Squaring Oracle, we can directly solve the CDH problem by computing $h^{a+b} = h^a \cdot h^b$, and then computing $h^{2ab} = h^{(a+b)^2} \cdot (h^{a^2})^{-1} \cdot (h^{b^2})^{-1}$, then a modular square root gives us $h^{ab}$

And there we are done.  (Showing the proof in the other direction isn't hard, but I'll leave that as an exercise for the reader)

Hence, if we have a generic way of solving your problem (e.g. by doing algebraic rearrangement of $g$ and $h_1$) that works in an arbitrary group, well, we just showed that the CDH problem is never hard, and we don't currently believe that.


Modular reduction for NIST prime P256-- understanding the data I am working on a project where I need to implement elliptic curve cryptography, I am struggling from a long time in order to understand the working and the process.

Modular finite field arithmetic, I understood the initial concept, now I am looking at this document from NIST

https://www.nsa.gov/ia/_files/nist-routines.pdf

However, I cannot understand, that if I need to check my modular adder or multiplier, what data should I use.

What is A,B and mod(P) in this document for P-256.
I want to implement montgomery reduction however I am not understanding it. I have a 512 bit value that is A*B. How should I move further from here.

IMP--Using the Fast reduction given by NIST ... how do we do it .... just add and subtract them and then find mod or find mod after every add or subtract?

REDUCTION--- While reducing ... suppose I did all those 256 bit additions and subtractions, Should I use 512 bit adder? as carry may be much more than 1 bit.

I have very very less time left to design the whole system. Please help me understand it is that I could implement it as soon as possible.
I am implementing the design on FPGA using VHDL.

In the document the P-256 parameters describe the curve P-256 on which you want to perform the operations. Traditionally a curve is represented in Weierstrass-form as the set of points for which

$$y^2\equiv x^3 + ax+b \pmod p$$

holds. Where $p$ is the prime defining the field for the operation and $a$ and $b$ define the shape of the curve. A point on the curve is a pair $(x,y)$ for which the above equation holds.

Now in order for elliptic curves to be actually useful, we want to perform operations on them. Usually this addition of two points, like $R=S+T$ with $R,S,T$ being curve points and we want to double points and thereby allow for fast exponentiation using the repeated square and multiply algorithm (although in practice you'd be more clever to avoid timing attacks). Doubling is usually denoted as $R=2S$ with $R,S$ being points on the curve.

Now to the basics on how to actually double and add two points. This is indeed described in the linked document. For reasons of efficiency, usually a third component for the points is defined $z$. If you have a point given only as $(x,y)$, define $z=1$. For practical applications I strongly suggest to simply follow the algorithms given in the document.

For verification you can use the below equations and the test vectors from the document. Note that for each section of the samples the parameters of that section need to be used.

To add two points $R=(x_R,y_R,z_R)$ and $S=(x_S,y_S,z_S)$ you can use the following equations to get $T=(x_T,y_T,z_T)$:
$$u=y_R\cdot z_S - y_S\cdot z_R\bmod p$$
$$v=x_R\cdot z_S - x_S\cdot z_R\bmod p$$
$$w=u^2\cdot z_R \cdot z_S - v^3 - 2v^2 x_S\cdot z_R\bmod p$$
$$x_T=vc \bmod p$$
$$y_T=u(v^2x_S\cdot z_R-w)-v^3y_S\cdot z_R \bmod p$$
$$z_T=z_S\cdot z_R v^3 \bmod p$$

And finally you calculate the modular inverse of $z_T$ and calculate the affine coordinates of the resulting points as $x_T=x_T\cdot z_T^{-1} \bmod p$ and $y_T=y_T\cdot z_T^{-1} \bmod p$ giving you again the "classical representation".

This is "only" the addition law for two distinct points. Doubling is similarly complicated and should be implemented by strictly following the specified algorithms.
If you really want to learn more about EC crypto you may find more answers in the Handbook of Elliptic and Hyperelliptic Cruve Cryptography. The above algorithm is taken from Introduction to modern Cryptography (Second edition).


Any famous approach for analyzing the randomness of data? I'm writing a function that will allow me to analyze the randomness of some input data and return some stats about the probability of this data to be random.
Obviously it should be based on two things:

How often each byte value is found / not found (randomness / distribution)

And how much data we have (certainty)

So among the outputs of my function will be two values:

"randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)
"randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

Is there a famous approach for this or I have to rethink the whole logic from scratch? This is probably something widely used in cryptography because this is how we can test keys: the decrypted data is highly random until the key is right.
I'm not looking for any particular language, just the math/logic approach.
One thing that puzzles me is: What does 50% randomness correspond to? Is it a subjective thing (like an art...) or math has some scientific ways to define what "50% randomness" means.

In terms of a measure of randomness, the usually accepted measure is Shannon entropy. In this sense for example 2 random bits which are 00 1/2 of the time, 01 1/4 of the time, 10 1/8 of the time and 11 1/8 of the time would represent 1.75 bits of random (from $\frac12+2\times\frac14+3\times\frac18+3\times\frac18$).
In your example then, if we sample $N$ bytes and byte $i$ comes up $b_i$ times we compute $p_i=b_i/N$ and then sum
$$-\sum_ip_i\log_{256}p_i$$
and that is the "proportion" of a byte's worth of random that you are getting with each byte. By taking $N$ larger you get a tighter confidence interval for your estimate and I'll defer to better statisticians on the details.
BUT note that if you generate bytes just by listing them 0, 1, 2,..., 255, 0, 1, 2... then this will score (very close to) 1 even though most people would say this is not very random at all.
For a measure of how likely a sample is to be producing uniform random bytes, you should perform a Pearson $\chi^2$ test on the data.
For more general randomness tests also consider Marsaglia's Diehard tests.