Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I need to decrypt a huge file that I own previously encoded by myself with a RSA public key (it's possible for this step using a symmetric algorithm key). Problem is that I can't load it in my disposable memory for specific embedded architecture reasons.

I need to decrypt it with the private key associated to the identity of that architecture (or the shared symmetric case if there were the algorithm chosen). I want to know if its possible to decrypt the file loading it in memory by parts and decrypting each of them, without losing security against brute force attacks. As far as I know, in a typical RSA encoding process first you transform the whole char string that is the file into a number, to be encrypted, so my assumption is that is not possible in a typical RSA encoding-decoding process. However, as I have the file I can encrypt it line by line or char by char, instead of encoding the whole, to decrypt it later again slice by slice. I'm assuming that a line or a char after encryption would have the same length in bytes, which may be a wrong assumption.

EDIT: Let's complicate things a little bit more: After decrypting through RSA or symmetric key, I'll have to encrypt again the slices of my huge file, this time with a RSA public key. So, first: Encrypting huge file on a custom basis to make it decryptable part by part; second: take each part and encrypt it with RSA.

Is this a feasible solution? Am I losing efficiency and would be more exposed to brute force attacks?

EDIT2: Keysizes would be the typical for opensource implementations: a minimum of 256bits. I've to investigate the hybrid encryption, can't tell yet. When I say a line I mean chunks of data of, let's say, 50-60 chars. I pretend to encrypt-decrypt a binary file, so char length doesn't matter (consider them 1 bytes ASCII if it helps)

share|improve this question

closed as unclear what you're asking by tylo, CodesInChaos, owlstead, e-sushi, Gilles Jun 14 at 21:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Your question is not clear: are you designing a storage format for that file, or do you have the encrypted file already stored? If the latter, you need to tell us how that file was produced. As the answers here explain, what you're describing, with a huge file somehow encrypted with RSA, is highly atypical. RSA only lets you encrypt a few hundred bits at a time, and slowly, so it's normally used to encrypt a symmetric key which is used to encrypt the rest. –  Gilles Jun 13 at 10:06
    
There is just not enough to go for in this question. Is some knd of hybrid encryption used? What's the keysize? What length is this "line" you're speaking of? Are you talking about usual ASCII chars there? Any other unit than bits and bytes is just not specific enough. And nto your last question: No, unless this "line" has exactly as many bits as your modulus in RSA, it will not be the same length (assuming you use RSA for that operation). –  tylo Jun 13 at 11:06
    
With the edit things get even more confused since RSA private keys aren't used for encryption. –  CodesInChaos Jun 13 at 14:30
    
@CodesInChaos My bad. I meant "this time with a RSA public key" –  Alex Jun 13 at 18:40
    
If the data is really already encrypted, give us the encryption format used; "RSA" just does not cut it. Else, change the question on the tune of "what would be an appropriate RSA-based file encryption format given that I want to..". In any case, please tell us your security goals; in particular, if it is an issue that an adversary can guess something about the relation between old and new data (including but not limited to: what changed?) [reposted with fix] –  fgrieu Jun 14 at 10:18
add comment

2 Answers 2

up vote 1 down vote accepted

As far as I know, in a typical RSA encoding process first you transform the whole char string that is the file into a number, to be encrypted, so my assumption is that is not possible in a typical RSA encoding-decoding process.

That's not typical. A typical real world RSA encryption process uses hybrid encryption, encrypting the data with a single-use symmetric key that is then encrypted using the actual RSA algorithms.

Depending on what the symmetric encryption is, you may be able to "seek" within the encrypted file without decrypting other parts. In most cases you'll at least be able to read it from the start and throw away decrypted parts as you go, avoiding excessive memory use.

However, as I have the file I can encrypt it line by line or char by char, instead of encoding the whole, to decrypt it later again slice by slice. I'm assuming that a line or a char after encryption would have the same length in bytes, which may be a wrong assumption.

Is this a feasible solution? Am I losing efficiency and would be more exposed to brute force attacks?

Using context-dependent (e.g. lines) blocking could leak data on the plaintext, so I wouldn't recommend it.

If you need to be able to quickly jump within the encoded file, you should use a symmetric encryption algorithm (under RSA if you want) that makes this easy. For example, AES in CTR or CBC modes. You will not be able to safely modify a small part of the file, but for read-only access that would be fine.

EDIT: Let's complicate things a little bit more: After decrypting through RSA or symmetric key, I'll have to encrypt again the slices of my huge file, this time with a RSA private key. So, first: Encrypting huge file on a custom basis to make it decryptable part by part; second: take each part and encrypt it with RSA.

I.e. the file is read-write?

In that case, I would divide the file into constant-sized blocks that get independently encrypted using any symmetric encryption algorithm that accepts a large nonce (24+ bytes would be good, but 16 at the very least). Generate a single symmetric encryption key, which you encrypt with RSA. For each block generate a random nonce/IV that gets prepended to the ciphertext. When something is modified, rewrite the whole block(s), generate new random nonces.

Block size should be chosen to balance the memory expansion caused by nonces with the write amplification caused by rewriting blocks. Something like 4KiB blocks would probably be OK, I would think.

Instead of random nonces, one could use an incrementing counter, but in that case there might need to be additional safeguards to prevent an attacker feeding you an old version of the file, so random nonces are simpler.

share|improve this answer
    
Not only the file is read-write. I cannot trust the kernel and there could be a binary injection at any time EXCEPT in the library taking care of decription and later encryption again and EXCEPT in the slice I loaded to decrypt. Unfortunatelly I don't have much information at this time about how the later RSA encryption is done. What was really important for me is to know if I can decrypt a binary file slice by slice and not as a whole. Transmitting the symmetric key is neither a problem: It will be stored with confidentiality. –  Alex Jun 13 at 18:47
1  
@Alex, I don't understand your threat model. If a computer is compromised at the kernel level, you can't store a private key on it. There's nothing you can do at that point to ensure secrecy of anything that happens on it. Anyway, yes, encryption and decryption can be done by slice, but you should most likely do it with symmetric encryption, like I wrote above. –  otus Jun 13 at 18:56
    
It is sure a non-conventional model but the keys. RSA or symmetrical will be in a confidential area. No fear about that. As I said I was concerned about the possibility of not being able to decrypt a big file in parts, which was a complete impede for me. Apart of that, there will be unavoidable problems like the one I mentioned above for which my solution is not perfect as is based in random accesses to check integrity when I assume the OS could try to tamper the file once it has been completely decrypted. –  Alex Jun 13 at 19:06
    
The file can be even hashed, but for my specs, it would be useless as we can assume than the decrypted huge file could be tampered any time, and that I would need to check the hash again piece by piece. It could even happen that the file gets tampered and faked original again right before I examine them chunk by chunk. –  Alex Jun 13 at 19:19
    
The best thing I could think of is wait to decrypt the hash and a part of the file in the safe area, then write the decrypted chunk of the file in the unpretected area and check is precisely at that moment, while a malicious SO starts to calculate a new hash to try to fool the architecture is modifying one of the chunks. It would be merely a matter of luck to trigger an alarm. –  Alex Jun 13 at 19:20
add comment

As I already wrote at http://math.stackexchange.com/questions/832652/rsa-decrypting-of-a-huge-file-by-parts, it is you, who knows the encryption details! But normally it is a misuse of RSA to encrypt large files. RSA works up to the key size (typically max 2048 or 4096 bit), therefore you must have encrypted the huge file using these small chunks, and decryption also has to work on these. As I see there are two scenarios:

  1. If you did the encryption with just one RSA encryption primitive, you have no chance to recover the plain text, example: From $1234567^7 = 126\; \mathrm{mod}\;(11*13)$, there is no realistic way to get back the $1234567$ from the $126$.

  2. You have encrypted in say 2048 bit chunks and have written the result chunks as hex (i.e. 512 chars per chunk) to the file. Then you can reverse the process.

share|improve this answer
add comment

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