I have a 130-160 characters message that I need to split in say, 3 parts, and be able to reconstruct it by recovering all 3 parts. I also need that these parts are type-able, meaning that they can't be too long (I mean not much longer than the original message), and they can't contain weird characters.

I tried with Shamir but the results are too long. I used PassGuardian for that.

Any suggestions?

You can also help me with the tags so the right people is able to find this post.

  • $\begingroup$ If the $160$ characters are arbitrary among $256$ values, and the set of type-able characters has $64$ values, then by a counting argument you need one of the $3$ parts to have $\lceil{160\over 3}\cdot{{\log_2(256)}\over{\log_2(64)}}\rceil=72$ characters, which is hardly type-able. Without arbitrary, you could compress the message beforehand. $\endgroup$ – fgrieu Jun 5 '13 at 11:26
  • $\begingroup$ @fgrieu I can type up to the length of the original message, so 72 characters is fine. But how do I do that? (does the algorithm have a name?) I'm sorry I'm not a cryptographer, just a developer. $\endgroup$ – ChocoDeveloper Jun 5 '13 at 12:05
  • 1
    $\begingroup$ What are your security goals? From the description it seems like taking the 130-160 character message $m=m_1||m_2||m_3$ (with $m_x$ being between 43 and 53 characters) and splitting it into $m_1$,$m_2$, and $m_3$ would be a valid solution. As it apparently is not: What are your security goals? $\endgroup$ – Maeher Jun 5 '13 at 12:19

If the requirement is being able to reconstruct a message of $1280=160\cdot 8$ bits from $3$ parts that are among a set of $2^6$ type-able characters (say $10$ digits, $26$ uppercase letters, $26$ lowercase letters, and $2$ other characters, as in Base64), then no cryptography is required. Simply:

  • split the $1280$ bits of the message into $3$ nearly equaly-sized segments, here of $427$, $427$ and $426$ bits;
  • append to each segment something allowing to order the $3$ segments and making them a multiple of $6$ bits, e.g. here 00000,00001, 000010; now all messages are $432=72\cdot6$ bits, the two right bits identify the segment number;
  • encode each segment as $72$ type-able characters, each encoding $6$ bits.

Decoding, identifying and pasting together the segments is easy and left as an exercise to the reader.

If there is the additional requirement that knowledge of $2$ of the $3$ encoded segments should give no useful information about the message, then we need some cryptography. One simple method, optimized to reduce message expansion, is:

  • generate a random 128-bit $K$;
  • encipher the message with key $K$ (say using AES in CTR mode with implicit null IV);
  • split the enciphered message in $427$, $427$ and $426$ bits data segments as above;
  • XOR the first $128$ bits of each of the segments, and $K$, forming $K'$;
  • splits $K'$ into $3$ segments of $42$, $43$, and $43$ bits, append these to the respective data segments, and append the terminations 00000,0001, 00010, forming $3$ segment of $474=79\cdot6$ bits, that can be identified by their rightmost 2 bits;
  • encode each segment as $79$ characters each encoding $6$ bits.

Decoding is easy:

  • decode each segment of $79$ characters into $3$ segments of $474$ bits;
  • identify each segment by its right two bits;
  • remove the terminations, rebuilt $K'$, remove these;
  • XOR the first $128$ bits of each of the segments, and $K'$, forming $K$;
  • rebuilt the enciphered message;
  • decipher it using $K$.

If any of the encoded segments is missing, $K$ can't be formed again.

Notice that we must expand the message with random data somehow, or loose semantic security.

| improve this answer | |
  • $\begingroup$ Yes, I needed that additional requirement. Thanks! $\endgroup$ – ChocoDeveloper Jun 5 '13 at 22:08
  • $\begingroup$ +1 for a working 3-of-3 approach. I'm pretty sure tha 2-of-3 (or X-of-Y) threshold schemes require longer messages; one approach is the very similar ssss and SecretSplitter. $\endgroup$ – David Cary Jun 6 '13 at 4:33
  • $\begingroup$ @David Cary: Common threshold schemes based on Shamir secret sharing are provably secure without assuming security of a block cipher, but (even in X-Y mode with X=Y) require much longer messages than what I propose. I had to craft a scheme to solve the "results are too long" issue worded in the question. $\endgroup$ – fgrieu Jun 6 '13 at 4:48
  • $\begingroup$ Yes, your scheme is a pretty clever way to reduce the size. $\endgroup$ – David Cary Jun 6 '13 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.