Author |
Topic: Security by obscurity in 100 bits (Read 982 times) |
|
ephyzy
Newbie
Gender: 
Posts: 27
|
 |
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: 27
|
|
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: 27
|
|
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 |
|
|
|
ephyzy
Newbie
Gender:
Posts: 27
|
|
Re: Security by obscurity in 100 bits
« Reply #4 on: Nov 19th, 2024, 2:47am » |
Quote Modify
|
Any ideas or takers for the alternative problem statement? My Python code in 2016 was actually wrong, as I found out about a month later. Seeking a non-brute force method if possible. The upper limit of N is 10^9.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print