wu :: forums « wu :: forums - Security by obscurity in 100 bits » Welcome, Guest. Please Login or Register. Aug 10th, 2022, 12:31pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, Grimbal, Eigenray, SMQ, towr, Icarus, ThudnBlunder)    Security by obscurity in 100 bits « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Security by obscurity in 100 bits  (Read 830 times)
ephyzy
Newbie

Gender:
Posts: 26
 Security by obscurity in 100 bits   « on: Jun 13th, 2016, 4:31am » Quote Modify

A "security by obscurity" system uses a 100 bits access code, with only 12 bits set. On the first day, it had a random access code of 100 bits. Then at the end of the day, it collects all the N intrusion attempts for the day (each one is 100 bits, with only 6 set bits) and updates its access code for the next day.
This update is done in such a way that:
- a% is correct on any 6 set bits,
- b% is correct on any 5 set bits,
- c% is correct on any 4 set bits,
- d% is correct on any 3 set bits,
- e% is correct on any 2 set bits
- f% is correct on any 1 set bit
- g% is correct on no set bits
- If all the bits set by the above 7 rules are less than 12, the system sets some random bits to make up the 12.

Q1: How must the new access code be generated at the end of the day, in terms of N intrusion attempts and the positive real numbers a, b, c, d, e, f, g (generated by the system such that the sum of these 7 is exactly 100)?

Q2: Question 1, but for fixed values of a,b,c,d,e,f and g on every day.

P.S. The system only provides direct access to set 6 bits. An intruder does not know that it is 12 bits that will need to be set, as the other 6 bits are hidden.
 « Last Edit: Jun 13th, 2016, 5:40am by ephyzy » IP Logged
ephyzy
Newbie

Gender:
Posts: 26
 Re: Security by obscurity in 100 bits   « Reply #1 on: Jun 14th, 2016, 4:01am » Quote Modify

Alternative problem statement:

Each of matrices P, Q, R is a column matrix with 100 bit binary numbers.

Given a matrix P, where each entry has exactly 6 set bits but the rows are not necessarily identical. What strategies / procedures can be used to generate a matrix Q with identical rows (some binary number with any 12 bits set) such that upon taking a bitwise AND of P and Q (i.e. P & Q) we may obtain any matrix R whose entries have set bits that have a known statistical distribution between 0 and 6?
 « Last Edit: Jun 14th, 2016, 4:02am by ephyzy » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Security by obscurity in 100 bits   « Reply #2 on: Jun 18th, 2016, 1:14pm » Quote Modify

I don't really fancy my chances that it's even possible to get close to a given statistical distribution.
If it is, brute force seems almost doable, 100!/(88! * 12!) is only in the order of 10^15.
How large is N?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ephyzy
Newbie

Gender:
Posts: 26
 Re: Security by obscurity in 100 bits   « Reply #3 on: Jun 18th, 2016, 2:06pm » Quote Modify

@towr:
Thanks! N can be as large as possible, and that's why I am wondering if there is a more efficient way to solve the problem that will scale well even for large N.

I eventually solved this in a way that involves minimal randomization (successively choosing 2 or 3 random integers), and also involves some bitwise OR and AND operations, but I feel sure there is probably a better way to do it.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board