Bis Ende Flashcards
TRIE
Unterscheid PATRICIA und PAT-tree
PAT-Trees preprocess a text for searching patterns.
Sisstring
Page Rank
- between 0 and 1
- likelihood to be visited by a person randomly surfing the web an following links
- Weight x
- 1/N: probability to visit A when being selected randomly out of all documents
- sum of ranks of all documents which link to A, divided by their number of outgoing links
Page Rank ausrechnen
putting the ranks of the latest iteration into the formula until the values converge
Data Encryption Standard
- 64 bit key in 54 by ignoring every 8th bit
- permutation table: alt in Tabelle -> neue Postition in Tabelle
- round keys: dividing 54 into 28 bit halves and left shifting in q cyclic way
- different bits of the key are used in each of the 16 rounds of the DES, which is one of the strengths of this algorithm
- number of weak keys however is quite small (about 64)
Hexadecimal
DES
S-box
- nonlinear
- safety of DES
- each S-box is a 4x16 table
- In DES there are 8 fixed S-Boxes
- S-box reduces the amount of bits Input: 6 bits -> output: 4 bits
S-box nonlinear Beweis
- und letzte = Zeile
- dazwischen = Spalte
- bei 0 anfangen zu zählen
linearity would allow for attacks with easy linear algebra.
RSA
Explain how a search engine would proceed in order to return the relevant documents for our query and write down the mathematical formulas.
- eliminate all documents which do not contain any of the query terms
- number of times each query term occurs in each document, the so-called term frequency tfij (with i being the term and j being the document)
- inverse document frequency factor idfi: weight of terms that occur very frequently in the collection and increases the weight of terms that occur rarely.
- dividing the number of all documents (here: n) by the number of documents containing the term (document frequency dfi)
Take into consideration that some documents might be (a lot) larger than others. What problem might occur regarding our query terms and how can we prevent this problem.
- we need to normalize this count in order to prevent a bias towards longer documents to give a measure of the importance
- Nenner: to the maximum term frequency of any term occurring in the document dj
What could you do in order to improve the relevance of one of your documents? Which actions are considered manipulation?
search engine optimization (SEO)
on-/off-page factors
punish manipulations by giving the document a low relevance
- Term-/Keyword-frequency: use certain keywords very often (clever writing or spamming/doorway page)
- Link structure: Documents linking to your document improve its rating (link farms)
cryptology
- Confusion
- Diffusion
- One-Time Pad
- obscures the relationship between plaintext and ciphertext characters (e.g. substitution)
- dissipates the redundancy of the plaintext (e.g. permutation); diffusion alone is easily cracked
- only provably safe encryption technique: random key of the same length as the plaintext is generated and only used once
What are the requirements for a public key cryptosystem?
Data Encryption Algorithms
only differ at 22 positions of the 64-bit positions in total.
If this problem occurs for many plaintexts, then the avalanche effect is not working well enough.
Without the avalanche effect (especially provided by the S-boxes), the differential cryptanalysis would be facilitated.
RSA
Requirements
RSA
Choice of N, c und d
RSA
Encryption
CFM & OFB
Assume that, due to a transmission error, one bit is changed in a cipher block somewhere in C. Explain the advantages and disadvantages of the error propagation in OFB!
Consider the following example: After Eve has inserted the 0 in plaintext P′, she observes the ciphertext C′. Try to decrypt the suffix of P.
four requirements of good cryptographic hash functions
Diffie-Hellmann
- if p is a prime of at least 300 digits, and a and b are at least 100 digits: discrete logarithm problem (can not be computed in realistic time using public information)
- The problem here: authenticity of Alice and Bob is not validated
Explain why the RSA algorithm can currently be regarded as a very safe encryption method.
Which future developments can decrease the security of RSA in a significant way?
- strength of RSA lies in the factorisation problem
- exponential time complexity
- currently practically infeasible to compute p and q
- quantum computer
advantages and disadvantages of RSA compared to a symmetric-key method
Ad
- secure key exchange: RSA the secret key (private key) is not transmitted, only the public key.
- public key system allows everybody to send encrypted messages without prior com- munication with the receiver.
- In RSA, communication between k partners requires only k key pairs.
DisAd
- High computational cost for encryption and decryption: too large to be used on large amounts of data. This is why RSA is often used in combination with other symmetric methods
- easy to break if there are only few possible plaintext messages.
A hacker makes copies of the Ecash money files you have stored on your computer. Can he spend the money? Explain your answer!
- digital bank notes are not associated with a person, but with the emitting bank
- respective bank keeps track of all serial numbers of the spent and signed bank notes, so that these notes can only be used once
What is the purpose of the dual signature used in the SET-protocol?
- accountability and traceability are restricted
- The purpose is to have a combination of order and payment information in the signature without disclosing the order to the bank and the payment information to the merchant.
Why does it make sense to apply a hash function on the secure passphrase?
compress passphrases of arbitrary length to fixed length keys, does not increase the security
entropy is in fact reduced
hashing the hash itself for a large number of times increases the time an attacker spends
Explain the reasons which justify the use of a separate data key.
when you have a separate data key, you just have to de- and reencrypt the single key, which can be done in an instance
With a separate data key, you can generate a copy of this key and let your colleague encrypt it with his personal passphrase
Why are asymmetric-key methods like RSA better suited for digital signatures compared to symmetric-key methods?
- signature needs to be associated with one person
- private key is the unique thing that clearly identifies a person
- exists in asymmetric-key methods and not in symmetric-key methods
Explain what certification authorities are and why they are necessary.
- officially institution which guarantees the validity and the correctness of public keys with
- a key certificate
- -> verify the signature is the public key of the correct person
- prevents: man- in-the-middle attack
